Discrete Mathematics & Theoretical Computer Science, Vol 13, No 1 (2011)

Font Size:  Small  Medium  Large

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