The Grid-Minor Theorem Revisited

Vida Dujmović, Robert Hickingbotham, Jędrzej Hodor, Gwenaël Joret, Hoang La, Piotr Micek, Pat Morin, Clément Rambaud, David R. Wood

Research output: Contribution to conferenceAbstractpeer-review

1 Citation (Scopus)

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.

Original languageEnglish
Pages1241-1245
Number of pages5
DOIs
Publication statusPublished - 2024
EventAnnual ACM-SIAM Symposium on Discrete Algorithms, 2024 - Westin Alexandria Old Town, Alexandria, United States of America
Duration: 7 Jan 202410 Jan 2024
Conference number: 35th
https://www.siam.org/conferences/cm/conference/soda24

Conference

ConferenceAnnual ACM-SIAM Symposium on Discrete Algorithms, 2024
Abbreviated titleSODA 2024
Country/TerritoryUnited States of America
CityAlexandria
Period7/01/2410/01/24
Internet address

Cite this