Grigoriev, Alexander - Tree-width and large grid minors in planar graphs

dmtcs:539 - Discrete Mathematics & Theoretical Computer Science, February 9, 2011, Vol. 13 no. 1
Tree-width and large grid minors in planar graphs

Authors: Grigoriev, Alexander

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(n(2) log n) time.


Volume: Vol. 13 no. 1
Section: Graph and Algorithms
Published on: February 9, 2011
Submitted on: September 22, 2009
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Consultation statistics

This page has been seen 110 times.
This article's PDF has been downloaded 700 times.