Paper by Erik D. Demaine

Reference:

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.

BibTeX

@Article{GridMinors_Combinatorica,
  AUTHOR        = {Erik D. Demaine and MohammadTaghi Hajiaghayi},
  TITLE         = {Linearity of Grid Minors in Treewidth with
                   Applications through Bidimensionality},
  JOURNAL       = {Combinatorica},
  journalurl    = {http://www.springerlink.com/content/1439-6912/},
  VOLUME        = 28,
  NUMBER        = 1,
  MONTH         = {January},
  YEAR          = 2008,
  PAGES         = {19--36},

  withstudent   = 1,
  length        = {13 pages},
  replaces      = {GridMinors_SODA2005},
  papers        = {GridMinors_SODA2005},
  doi           = {https://dx.doi.org/10.1007/s00493-008-2140-4},
  dblp          = {https://dblp.org/rec/journals/combinatorica/DemaineH08},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1007/s00493-008-2140-4">SpringerLink</A>.},
}

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.

Comments:

This paper is also available from SpringerLink.

Length:

The paper is 13 pages.

Availability:

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)