Paper by Erik D. Demaine

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.

BibTeX

@InProceedings{GridMinors_SODA2005,
  AUTHOR        = {Erik D. Demaine and MohammadTaghi Hajiaghayi},
  TITLE         = {Graphs Excluding a Fixed Minor have Grids as Large as
                   Treewidth, with Combinatorial and Algorithmic Applications
                   through Bidimensionality},
  BOOKTITLE     = {Proceedings of the 16th Annual ACM-SIAM Symposium on
                   Discrete Algorithms (SODA 2005)},
  bookurl       = {http://www.siam.org/meetings/DA05/},
  ADDRESS       = {Vancouver, British Columbia, Canada},
  MONTH         = {January 23--25},
  YEAR          = 2005,
  PAGES         = {682--689},

  withstudent   = 1,
  length        = {8 pages},
  ee            = {http://dl.acm.org/citation.cfm?id=1070432.1070528},
  papers        = {GridMinors_Combinatorica},
  dblp          = {https://dblp.org/rec/conf/soda/DemaineH05a},
}

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)