**Reference**:- Erik D. Demaine and MohammadTaghi Hajiaghayi, “Graphs Excluding a Fixed Minor have Grids as Large as Treewidth, with Combinatorial and Algorithmic Applications through Bidimensionality”, in
*Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005)*, Vancouver, British Columbia, Canada, January 23–25, 2005, pages 682–689. **Abstract**:-
We prove that any
*H*-minor-free graph, for a fixed graph*H*, of treewidth*w*has an Ω(*w*) × Ω(*w*) grid graph as a minor. Thus grid minors suffice to certify that*H*-minor-free graphs have large treewidth, up to constant factors. This strong relationship was previously known for the special cases of planar graphs and bounded-genus graphs, and is known not to hold for general graphs. The approach of this paper can be viewed more generally as a framework for extending combinatorial results on planar graphs to hold on*H*-minor-free graphs for any fixed*H*. Our result has many combinatorial consequences on bidimensionality theory, parameter-treewidth bounds, separator theorems, and bounded local treewidth; each of these combinatorial results has several algorithmic consequences including subexponential fixed-parameter algorithms and approximation algorithms. **Length**:- The paper is 8 pages.
**Availability**:- The paper is available in PostScript (286k), gzipped PostScript (101k), and PDF (160k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- GridMinors_Combinatorica (Linearity of Grid Minors in Treewidth with Applications through Bidimensionality)

See also other papers by Erik Demaine.

Last updated May 16, 2024 by Erik Demaine.