Edge separators for graphs excluding a minor

Abstract

We prove that every $n$-vertex $K_t$-minor-free graph $G$ of maximum degree $\hat{I}”$ has a set $F$ of $O(t^2(\log t{)}^{1/4}\sqrt{\hat{I}”n})$ edges such that every component of $G-F$ has at most $n/2$ vertices. This is best possible up to the dependency on $t$ and extends earlier results of Diks, Djidjev, Sykora, and VrÅ¥o (1993) for planar graphs, and of Sykora and VrÅ¥o (1993) for bounded-genus graphs. Our result is a consequence of the following more general result: The line graph of $G$ is isomorphic to a subgraph of the strong product $H⊠K_{\lfloor p\rfloor }$ for some graph $H$ with treewidth at most $t-2$ and $p=\sqrt{(t-3)\hat{I}”|E(G)|}+\hat{I}”$.