b'David R. Wood'

research

∙ 07/06/2023

The grid-minor theorem revisited

We prove that for every planar graph X of treedepth h, there exists a po...

0 Vida Dujmovic, et al. ∙

research

∙ 06/09/2023

Proof of the Clustered Hadwiger Conjecture

Hadwiger's Conjecture asserts that every K_h-minor-free graph is properl...

0 Vida Dujmovic, et al. ∙

research

∙ 03/27/2023

The Excluded Tree Minor Theorem Revisited

We prove that for every tree T of radius h, there is an integer c such t...

0 Vida Dujmovic, et al. ∙

research

∙ 08/22/2022

Product structure of graph classes with strongly sublinear separators

We investigate the product structure of hereditary graph classes admitti...

0 David R. Wood, et al. ∙

research

∙ 07/14/2022

2-Layer Graph Drawings with Bounded Pathwidth

We determine which properties of 2-layer drawings characterise bipartite...

0 David R. Wood, et al. ∙

research

∙ 06/06/2022

Product structure of graph classes with bounded treewidth

We show that many graphs with bounded treewidth can be described as subg...

0 Rutger Campbell, et al. ∙

research

∙ 02/24/2022

Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)

In a reduction sequence of a graph, vertices are successively identified...

0 Édouard Bonnet, et al. ∙

research

∙ 02/10/2022

Three-dimensional graph products with unbounded stack-number

We prove that the stack-number of the strong product of three n-vertex p...

0 David Eppstein, et al. ∙

research

∙ 07/31/2021

An improved planar graph product structure theorem

Dujmović, Joret, Micek, Morin, Ueckerdt and Wood [J. ACM 2020] proved th...

0 Torsten Ueckerdt, et al. ∙

research

∙ 06/22/2021

Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond

Let G be a connected n-vertex graph in a proper minor-closed class 𝒢. We...

0 Manuel Aprile, et al. ∙

research

∙ 05/04/2021

Separating layered treewidth and row treewidth

Layered treewidth and row treewidth are recently introduced graph parame...

0 Prosenjit Bose, et al. ∙

research

∙ 11/09/2020

Stack-number is not bounded by queue-number

We describe a family of graphs with queue-number at most 4 but unbounded...

0 Vida Dujmovic, et al. ∙

research

∙ 09/04/2020

Nonrepetitive graph colouring

A vertex colouring of a graph G is "nonrepetitive" if G contains no path...

0 David R. Wood, et al. ∙

research

∙ 03/30/2020

Subgraph densities in a surface

Given a fixed graph H that embeds in a surface Σ, what is the maximum nu...

0 Tony Huynh, et al. ∙

research

∙ 02/13/2020

Notes on Tree- and Path-chromatic Number

Tree-chromatic number is a chromatic version of treewidth, where the cos...

0 Tony Huynh, et al. ∙

research

∙ 01/24/2020

Notes on Graph Product Structure Theory

It was recently proved that every planar graph is a subgraph of the stro...

0 Zdeněk Dvořák, et al. ∙

research

∙ 08/14/2019

Clustered Variants of Hajós' Conjecture

Hajós conjectured that every graph containing no subdivision of the comp...

0 Chun-Hung Liu, et al. ∙

research

∙ 07/11/2019

The structure of k-planar graphs

Dujmović et al. (FOCS 2019) recently proved that every planar graph is a...

0 Vida Dujmovic, et al. ∙

research

∙ 04/10/2019

Planar graphs have bounded nonrepetitive chromatic number

A colouring of a graph is "nonrepetitive" if for every path of even orde...

0 Vida Dujmovic, et al. ∙

research

∙ 04/09/2019

Planar Graphs have Bounded Queue-Number

We show that planar graphs have bounded queue-number, thus proving a con...

0 Vida Dujmovic, et al. ∙

research

∙ 01/17/2019

Queue Layouts of Graphs with Bounded Degree and Bounded Genus

We prove that graphs with bounded degree and bounded Euler genus have bo...

0 Vida Dujmovic, et al. ∙

research

∙ 10/19/2018

Minor-closed graph classes with bounded layered pathwidth

We prove that a minor-closed class of graphs has bounded layered pathwid...

0 Vida Dujmovic, et al. ∙

research

∙ 07/31/2018

Tight Upper Bounds on the Crossing Number in a Minor-Closed Class

The crossing number of a graph is the minimum number of crossings in a d...

0 Vida Dujmovic, et al. ∙

research

∙ 06/19/2018

Defective and Clustered Choosability of Sparse Graphs

An (improper) graph colouring has "defect" d if each monochromatic subgr...

0 Kevin Hendrey, et al. ∙

research

∙ 06/19/2018

Defective and Clustered Colouring of Sparse Graphs

An (improper) graph colouring has "defect" d if each monochromatic subgr...

0 Kevin Hendrey, et al. ∙

research

∙ 04/09/2018

Better bounds for poset dimension and boxicity

We prove that the dimension of every poset whose comparability graph has...

0 Alex Scott, et al. ∙

research

∙ 04/03/2018

The exact chromatic number of the convex segment disjointness graph

Let P be a set of n points in strictly convex position in the plane. Let...

0 Ruy Fabila-Monroy, et al. ∙

research

∙ 01/05/2018

Seymour's conjecture on 2-connected graphs of large pathwidth

We prove the conjecture of Seymour (1993) that for every apex-forest H_1...

0 Tony Huynh, et al. ∙

research

∙ 08/16/2017

Thickness and Antithickness of Graphs

This paper studies questions about duality between crossings and non-cro...

0 Vida Dujmovic, et al. ∙

David R. Wood

Featured Co-authors