A separator theorem for nonplanar graphs
Noga Alon, Paul D. Seymour, Robin B. Thomas · Journal of the American Mathematical Society · 1990
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 {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 ) (A,\;B,\;C) in time O ( h 1