Excluded Grid Theorem
Author:
Open Access
- 14 June 2015
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 645-654
Abstract
We study the Excluded Grid Theorem of Robertson and Seymour. This is a fundamental result in graph theory, that states that there is some function f:Z+→ Z+, such that for any integer g> 0, any graph of treewidth at least f(g), contains the (g x g)-grid as a minor. Until recently, the best known upper bounds on f were super-exponential in g. A recent work of Chekuri and Chuzhoy provided the first polynomial bound, by showing that treewidth f(g)=O(g98 poly log g) is sufficient to ensure the existence of the (g x g)-grid minor in any graph. In this paper we provide a much simpler proof of the Excluded Grid Theorem, achieving a bound of $f(g)=O(g^{36} poly log g)$. Our proof is self-contained, except for using prior work to reduce the maximum vertex degree of the input graph to a constant.
Keywords
Funding Information
- National Science Foundation (CCF-1318242)
This publication has 27 references indexed in Scilit:
- Degree-3 Treewidth Sparsifiers2014
- Polynomial bounds for the grid-minor theorem2014
- Poly-logarithmic Approximation for Maximum Node Disjoint Paths with Constant Congestion2013
- Maximum Edge-Disjoint Paths in k-Sums of GraphsLecture Notes in Computer Science, 2013
- The All-or-Nothing Multicommodity Flow ProblemSIAM Journal on Computing, 2013
- A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 22012
- Routing in undirected graphs with constant congestion2012
- Approximation Algorithms for the Edge-Disjoint Paths Problem via Raecke Decompositions2010
- A Graph Reduction Step Preserving Element-Connectivity and Applications2009
- Multicommodity flow, well-linked terminals, and routing problems2005