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 × g grid.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics