Paper by Erik D. Demaine

Erik D. Demaine and MohammadTaghi Hajiaghayi, “Linearity of Grid Minors in Treewidth with Applications through Bidimensionality”, Combinatorica, volume 28, number 1, January 2008, pages 19–36.

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.

This paper is also available from SpringerLink.

The paper is 13 pages.

The paper is available in PostScript (429k), gzipped PostScript (181k), and PDF (254k).
See information on file formats.
[Google Scholar search]

Related papers:
GridMinors_SODA2005 (Graphs Excluding a Fixed Minor have Grids as Large as Treewidth, with Combinatorial and Algorithmic Applications through Bidimensionality)

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated March 12, 2024 by Erik Demaine.