An Estimate of the Tree-Width of a Planar Graph Which Has Not a Given Planar Grid as a Minor

摘要

We give a more simple than in [8] proof of the fact that if a finite graph has no minors isomorphic to the planar grid of the size of r × r, then the tree-width of this graph is less than exp(poly(r)). In the case of planar graphs we prove a linear upper bound which improves the quadratic estimate from [5].