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.
展开▼
机译:我们证明,对于树宽为ω的固定图 H I>的任何 H I>次要图,都有一个Ω(ω)×Ω(ω)网格图作为次要图。因此,网格次要足以证明 H I>-次要图具有较大的树宽,并且直到恒定因子为止。这种强关系以前在平面图和有界属图的特殊情况下是已知的,而对于一般图则不成立。本文的方法可以更广泛地视为扩展平面图上组合结果的框架,以保持任意固定的 H的 H I>次要图。 I>在二维理论,参数树宽范围,分隔符定理和有界局部树宽方面有许多组合后果。这些组合结果中的每一个都有若干算法结果,包括次指数固定参数算法和逼近算法。
展开▼