The Grid-Minor Theorem Revisited
Vida Dujmovic, Robert Hickingbotham, Jedrzej Hodor, Gwenaël Joret, Hoang La, Piotr Micek, Pat Morin, Clément Rambaud, David R. Wood
Abstract
We prove that for every planar graph X of treedepth h, there exists a positive integer c such that for every X-minor-free graph G, there exists a graph H of treewidth at most f (h) such that G is isomorphic to a subgraph of H ⊠ Kc. This is a qualitative strengthening of the Grid-Minor Theorem of Robertson and Seymour (JCTB, 1986), and treedepth is the optimal parameter in such a result. As an example application, we use this result to improve the upper bound for weak coloring numbers of graphs excluding a given graph as a minor.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
4 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Proof of the Clustered Hadwiger Conjecture cites Improved bounds for centered colorings
- Proof of the Clustered Hadwiger Conjecture cites Approximating Pathwidth for Graphs of Small Treewidth
- Proof of the Clustered Hadwiger Conjecture cites Adjacency Labelling for Planar Graphs (and Beyond)
- Polynomial bounds for the Graph Minor Structure Theorem cites Proof of the Clustered Hadwiger Conjecture
- Weak coloring numbers of minor-closed graph classes cites Approximating Pathwidth for Graphs of Small Treewidth
- Centered colorings in minor-closed graph classes cites Improved bounds for centered colorings
Cited by top-tier papers4
- Proof of the Clustered Hadwiger ConjectureVida Dujmovic, Louis Esperet, Pat Morin, David R. WoodFOCS 2023 · 7 citations
- Polynomial bounds for the Graph Minor Structure TheoremMaximilian Gorsky, Michal T. Seweryn, Sebastian WiederrechtFOCS 2025 · 1 citation
- Weak coloring numbers of minor-closed graph classesJedrzej Hodor, Hoang La, Piotr Micek, Clément RambaudSODA 2025
- Centered colorings in minor-closed graph classesJedrzej Hodor, Hoang La, Piotr Micek, Clément RambaudSODA 2026
Builds on4
- Adjacency Labelling for Planar Graphs (and Beyond)Vida Dujmovic, Louis Esperet, Cyril Gavoille, Gwenaël Joret et al.FOCS 2020 · 31 citations
- Improved bounds for centered coloringsMichal Debski, Stefan Felsner, Piotr Micek, Felix SchröderSODA 2020 · 16 citations
- Proof of the Clustered Hadwiger ConjectureVida Dujmovic, Louis Esperet, Pat Morin, David R. WoodFOCS 2023 · 7 citations
- Approximating Pathwidth for Graphs of Small TreewidthCarla Groenland, Gwenaël Joret, Wojciech Nadara, Bartosz WalczakSODA 2021 · 6 citations
Related papers
- Catching Rats in H-minor-free GraphsMaximilian Gorsky, Giannos Stamoulis, Dimitrios M. Thilikos, Sebastian WiederrechtSODA 2026
- A quasi-polynomial bound for the minimal excluded minors for a surfaceSarah Houdaigoui, Ken-ichi KawarabayashiSODA 2026
- The Directed Flat Wall TheoremArchontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung KwonSODA 2020 · 13 citations
- Fixed-parameter tractability of graph isomorphism in graphs with an excluded minorDaniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket SaurabhSTOC 2022 · 4 citations
- The Erdős-Pósa property for circle graphs as vertex-minorsRutger Campbell, Jochen Pascal Gollin, Meike Hatzel, O-joung Kwon et al.SODA 2026 · 5 citations
