  Given an undirected graph with edge costs and node weights, the minimum
bisection problem asks for a partition of the nodes into two parts of equal
weight such that the sum of edge costs between the parts is minimized. We give
a polynomial time bicriteria approximation scheme for bisection on planar
graphs.
  Specifically, let $W$ be the total weight of all nodes in a planar graph $G$.
For any constant $\varepsilon > 0$, our algorithm outputs a bipartition of the
nodes such that each part weighs at most $W/2 + \varepsilon$ and the total cost
of edges crossing the partition is at most $(1+\varepsilon)$ times the total
cost of the optimal bisection. The previously best known approximation for
planar minimum bisection, even with unit node weights, was $O(\log n)$. Our
algorithm actually solves a more general problem where the input may include a
target weight for the smaller side of the bipartition.
