Tree-width and large grid minors in planar graphs
Alexander Grigoriev
Abstract
We show that for a planar graph with no g-grid minor
there exists a tree-decomposition of width at most
5g-6. The proof is constructive and simple. The
underlying algorithm for the tree-decomposition runs in
O(n2 log n) time.
Full Text: PDF PostScript