A separator theorem for nonplanar graphs

Abstract:

Let $G$ be an $n$-vertex graph with no minor isomorphic to an $h$-vertex complete graph. We prove that the vertices of $G$ can be partitioned into three sets $A,\;B,\;C$ such that no edge joins a vertex in $A$ with a vertex in $B$, neither $A$ nor $B$ contains more than $2n/3$ vertices, and $C$ contains no more than ${h^{3/2}}{n^{1/2}}$ vertices. This extends a theorem of Lipton and Tarjan for planar graphs. We exhibit an algorithm which finds such a partition $(A,\;B,\;C)$ in time $O({h^{1/2}}{n^{1/2}}m)$, where $m = \left | {V(G)} \right | + \left | {E(G)} \right |$.