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

dmtcs:539 - Discrete Mathematics & Theoretical Computer Science, February 9, 2011, Vol. 13 no. 1 - https://doi.org/10.46298/dmtcs.539
Tree-width and large grid minors in planar graphsArticle

Authors: Alexander Grigoriev ORCID1

  • 1 Department of Quantitative Economics [Maastricht]

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.

https://doi.org/10.46298/dmtcs.539
Source: HAL:hal-00990485v1
Volume: Vol. 13 no. 1
Section: Graph and Algorithms
Published on: February 9, 2011
Accepted on: June 9, 2015
Submitted on: September 22, 2009
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Share and export

Consultation statistics

This page has been seen 337 times.
This article's PDF has been downloaded 1434 times.