Partitioning Planar Graphs
Thang Nguyen Bui, Andrew M. Peck · SIAM Journal on Computing · 1992
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 \in [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 optimals-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(b^2 n^3 2^{4.5b} )$, where b is the number of edges cut by an optimal s-partition. In particular, by letting $s = \lfloor n/2 \rfloor $ 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 $\hat G$ of G is also given such that the embedding of each biconnected component in $\hat 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(m^2 n^3 2^{3m} )$ is also given.