×

Tree-width and large grid minors in planar graphs. (English) Zbl 1283.05072

Summary: 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.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C05 Trees
05C83 Graph minors
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: Link