Linearity of grid minors in treewidth with applications through bidimensionality |
| |
Authors: | Erik D Demaine Mohammadtaghi Hajiaghayi |
| |
Institution: | (1) MIT, Computer Science and Artificial Intelligence Laboratory, 32 Vassar Street, Cambridge, MA 02139, USA |
| |
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-minorfree 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.
A preliminary version of this paper appeared in the ACM-SIAM Symposium on Discrete Algorithms (SODA 2005) 16]. |
| |
Keywords: | 05C83 05C85 68R10 |
本文献已被 SpringerLink 等数据库收录! |
|