### Abstract

One of the key results in Robertson and Seymour's seminal work on graph minors is the Grid-Minor Theorem (also called the Excluded Grid Theorem). The theorem states that for every fixed-size grid H, every graph whose treewidth is large enough, contains H as a minor. This theorem has found many applications in graph theory and algorithms. Let f(κ) denote the largest value, such that every graph of treewidth κ contains a grid minor of size f(κ) × f(κ). The best current quantitative bound, due to recent work of Kawarabayashi and Kobayashi [15], and Leaf and Seymour [18], shows that f(κ) = Ω(√ log κ/ log log κ). In contrast, the best known upper bound implies that f(κ) = O(√ κ/ log κ) [22]. In this paper we obtain the first polynomial relationship between treewidth and grid-minor size by showing that f(κ) = Ω(k ^{δ}) for some fixed constant δ > 0, and describe an algorithm, whose running time is polynomial in |V (G)| and κ, that finds a model of such a grid-minor in G.

Original language | English (US) |
---|---|

Title of host publication | STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing |

Publisher | Association for Computing Machinery |

Pages | 60-69 |

Number of pages | 10 |

ISBN (Print) | 9781450327107 |

DOIs | |

State | Published - Jan 1 2014 |

Event | 4th Annual ACM Symposium on Theory of Computing, STOC 2014 - New York, NY, United States Duration: May 31 2014 → Jun 3 2014 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

Other | 4th Annual ACM Symposium on Theory of Computing, STOC 2014 |
---|---|

Country | United States |

City | New York, NY |

Period | 5/31/14 → 6/3/14 |

### Fingerprint

### Keywords

- Grid minor theorem
- Treewidth

### ASJC Scopus subject areas

- Software

### Cite this

*STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing*(pp. 60-69). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/2591796.2591813