Linearity of grid minors in treewidth with applications through bidimensionality
Linearity of grid minors in treewidth with applications through bidimensionality
复制标题
树宽中网格次要的线性及其通过二维的应用
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
M. Hajiaghayi
中科院分区：
文献类型：
--
作者：
E. Demaine;M. Hajiaghayi
证明了树宽为w的固定图H的任意无H-子式图都有一个Ω（w）× Ω（w）格图作为子式.因此，网格未成年人足以证明H-minorfree图有大的树宽，直到常数因子。这种强关系以前是已知的平面图和有界亏格图的特殊情况下，并已知不适用于一般图。本文的方法可以更一般地被看作是一个框架，用于扩展平面图上的组合结果，以保持对任何固定H的H-子项自由图。我们的结果有许多组合的后果，二维理论，参数树宽的界限，分离定理，有界局部树宽，这些组合的结果有几个算法的后果，包括次指数固定参数算法和近似算法。
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.