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 graphs

Authors: Alexander Grigoriev ORCID-iD

    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
    Accepted on: June 9, 2015
    Submitted on: September 22, 2009
    Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

    Share

    Consultation statistics

    This page has been seen 198 times.
    This article's PDF has been downloaded 1181 times.