Grigoriev, Alexander Tree-width and large grid minors in planar graphs. (English) Zbl 1283.05072 Discrete Math. Theor. Comput. Sci. 13, No. 1, 13-20 (2011). 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. Cited in 5 Documents MSC: 05C10 Planar graphs; geometric and topological aspects of graph theory 05C05 Trees 05C83 Graph minors 05C85 Graph algorithms (graph-theoretic aspects) Keywords:planar graph; tree decomposition; tree width; minor; grid graph PDFBibTeX XMLCite \textit{A. Grigoriev}, Discrete Math. Theor. Comput. Sci. 13, No. 1, 13--20 (2011; Zbl 1283.05072) Full Text: Link