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.


Source : oai:HAL:hal-00990485v1
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

Browsing statistics

This page has been seen 34 times.
This article's PDF has been downloaded 181 times.