Lune

SODA2024Top-tier venue

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.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

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
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers4

  1. Proof of the Clustered Hadwiger ConjectureVida Dujmovic, Louis Esperet, Pat Morin, David R. WoodFOCS 2023 · 7 citations
  2. Polynomial bounds for the Graph Minor Structure TheoremMaximilian Gorsky, Michal T. Seweryn, Sebastian WiederrechtFOCS 2025 · 1 citation
  3. Weak coloring numbers of minor-closed graph classesJedrzej Hodor, Hoang La, Piotr Micek, Clément RambaudSODA 2025
  4. Centered colorings in minor-closed graph classesJedrzej Hodor, Hoang La, Piotr Micek, Clément RambaudSODA 2026

Builds on4

  1. Adjacency Labelling for Planar Graphs (and Beyond)Vida Dujmovic, Louis Esperet, Cyril Gavoille, Gwenaël Joret et al.FOCS 2020 · 31 citations
  2. Improved bounds for centered coloringsMichal Debski, Stefan Felsner, Piotr Micek, Felix SchröderSODA 2020 · 16 citations
  3. Proof of the Clustered Hadwiger ConjectureVida Dujmovic, Louis Esperet, Pat Morin, David R. WoodFOCS 2023 · 7 citations
  4. Approximating Pathwidth for Graphs of Small TreewidthCarla Groenland, Gwenaël Joret, Wojciech Nadara, Bartosz WalczakSODA 2021 · 6 citations

Related papers

  1. Catching Rats in H-minor-free GraphsMaximilian Gorsky, Giannos Stamoulis, Dimitrios M. Thilikos, Sebastian WiederrechtSODA 2026
  2. A quasi-polynomial bound for the minimal excluded minors for a surfaceSarah Houdaigoui, Ken-ichi KawarabayashiSODA 2026
  3. The Directed Flat Wall TheoremArchontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung KwonSODA 2020 · 13 citations
  4. Fixed-parameter tractability of graph isomorphism in graphs with an excluded minorDaniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket SaurabhSTOC 2022 · 4 citations
  5. 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
Dusk over the sea between two cliffs drawn in fine vertical lines