PARTITIONING PLANAR GRAPHS

A common problem in graph theory is that of dividing the vertices of a graph into two sets of prescribed size while cutting a minimum number of edges. In this paper this problem is considered as it is restricted to the class of planar graphs. Let G be a planar graph on n vertices and s is-an-element-of [0, n] be given. An s-partition of G is a partition of the vertex set of G into sets of size s and n-s. An optimal s-partition is an s-partition that cuts the fewest number of edges. The main result of this paper is an algorithm that finds an optimal s-partition in time O(b2n(3)2(4.5b), where b is the number of edges cut by an optimal s-partition. In particular, by letting s = right perpendicular n/2 left perpendicular the immediate corollary that any planar graph with small (O(log n)) bisection width may be bisected in polynomial time is obtained. Furthermore, suppose that a planar embedding G of G is also given such that the embedding of each biconnected component in G is at most m-outerplanar (such an embedding is called m-outerplane-separable). An algorithm for finding optimal s-partition of G in time O(m2n(3)2(3)m) is also given.