The Grid-Minor Theorem Revisited

We prove that for every planar graph X of treedepth h, there exists a positive integer c such that for every X-minor-free graph G, there exists a graph H of treewidth at most f (h) such that G is isomorphic to a subgraph of H ⊠ Kc. This is a qualitative strengthening of the Grid-Minor Theorem of Robertson and Seymour (JCTB, 1986), and treedepth is the optimal parameter in such a result. As an example application, we use this result to improve the upper bound for weak coloring numbers of graphs excluding a given graph as a minor.