Shallow excluded minors and improved graph decompositions

Abstract

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(lh² log n + n/l). This, in turn, implies that any graph that excludes K_h 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 = \\Omega\\Gamma L d\\Gamma1 ) 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...