Publications with Gwenaël Joret
Minor-closed graph classes with bounded layered pathwidth.
V. Dujmović,
D. Eppstein,
G. Joret,
P. Morin, and
D. R. Wood.
arXiv:1810.08314.
SIAM J. Discrete Math 34 (3): 1693–1709, 2020, doi:10.1137/18M122162X.
A minor-closed graph family has a functional relation between diameter and path width (bounded local pathwidth) if and only if it excludes an apex-tree. The same graph families are also the ones with bounded layered pathwidth: a simultaneous path decomposition and layering (sequence of subsets of vertices with all edges connecting the same subset or consecutive subsets) so that the intersection of a bag and a layer has constant size.
Product structure extension of the Alon–Seymour–Thomas theorem.
M. Distel,
V. Dujmović,
D. Eppstein,
R. Robert Hickingbotham,
G. Joret,
P. Micek,
P. Morin,
M. T. Seweryn, and
D. R. Wood.
arXiv:2212.08739.
SIAM J. Discrete
Math. 38 (3): 2095–2107, 2024, doi:10.1137/23M1591773.
The graphs in any nontrivial minor-closed graph family can be represented as strong products of a graph of treewidth 4 with a clique of size \(O(\sqrt{n})\). For planar graphs and \(K_{3,t}\)-minor-free graphs, the treewidth can be reduced to 2.