A separator theorem for nonplanar graphs

Let G G be an n n -vertex graph with no minor isomorphic to an h h -vertex complete graph. We prove that the vertices of G G can be partitioned into three sets A , B , C A,\;B,\;C such that no edge joins a vertex in A A with a vertex in B B , neither A A nor B B contains more than 2 n / 3 2n/3 vertices, and C C contains no more than h 3 / 2 n 1 / 2 {h3/2}{n1/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 ) (A,\;B,\;C) in time O ( h 1 <mml:mrow class