×

zbMATH — the first resource for mathematics

Quickly excluding a planar graph. (English) Zbl 0807.05023
Summary: In an earlier paper, the first two authors proved that for any planar graph \(H\), every graph with no minor isomorphic to \(H\) has bounded tree- width; but the bound given there was enormous. Here we prove a much better bound. We also improve the best known bound on the tree-width of planar graphs with no minor isomorphic to a \(g\times g\) grid.

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite
Full Text: DOI