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
Last updated October 28, 2020 by