Linearity of grid minors in treewidth with applications through bidimensionality (Q949776): Difference between revisions

The \(r \times r\) grid has treewidth \(\Theta(r)\). \textit{N. Robertson, P. Seymour and R. Thomas} showed [J. Comb. Theory, Ser. B 62 No. 2, 323-348 (1994; Zbl 0807.05023)] that a planar graph of treewidth \(w\) has an \(\Omega(w) \times \Omega(w)\) grid as a minor. While in general this is not true, they also proved that for every fixed graph \(H\), every \(H\)-minor-free graph of treewidth larger than \(20^{5| V(H)| ^3r}\) has an \(r \times r\) grid as a minor. The authors sharpen that result proving that for every fixed graph \(H\), every \(H\)-minor-free graph of treewidth \(w\) has an \(\Omega(w) \times \Omega(w)\) grid as a minor. The theorem makes the description of an \(H\)-minor-free graph with given treewidth effective. Out of the several consequences let us single out an elegant generalization of \textit{R. J. Lipton} and \textit{R. E. Tarjan} [SIAM J. Comput. 9, 615-627 (1980; Zbl 0456.68077)]. It spells out as follows. For every fixed graph \(H\), every \(H\)-minor-free graph \(G\) has treewidth \(O(\sqrt{| V(G)| })\).