Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality

Erik D. Demaine, Mohammad Taghi HajiaghayiSODA 2005 · OpenReview

Abstract

We prove that any H-minor-free graph, for a fixed graph H, of treewidth ω has an Ω(ω) × Ω(ω) 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 con-sequences 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.
BibTeX
@inproceedings{demaine2005graphs,
  author = {Erik D. Demaine and Mohammad Taghi Hajiaghayi},
  title = {{Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality}},
  booktitle = {SODA},
  year = {2005},
  url = {https://openreview.net/forum?id=3yFH8KnPHS},
}

Loading related content...

Figure