Shallow excluded minors and improved graph decompositions

In this paper we introduce the notion of the limiteddepth minor exclusion and show that graphs that exclude small limited-depth minors have relatively small separators. In particular, we prove that for any graph that excludes K h as a depth l minor, we can find a separator of size O (lhsup2; log n + n/l). This, in turn, implies that any graph that excludes Kₕ as a minor has an O (h p n log n) -sized separator, improving the result of Alon, Seymour, and Thomas for the case where h AE p log n. We show that the d-dimensional simplicial graphs with constant aspect ratio, defined by Miller and Thurston, exclude K h minors of depth L for h = \\ L d\1) when d is a constant. These graphs arise in finite element computations. Our proof of separator existence is constructive and gives an algorithm to find the t-cut-covers decomposition, introduced by Kaklamanis, Krizanc, and Rao, in graphs that exclude small depth minors. This has two interesting implications. First, combina. . .