Status of Minimum Bisection on Planar Graphs

From himtp
Jump to: navigation, search

(suggested by Marek Karpinski)

It is well known that MAX-CUT on planar graphs can be solved exactly in polynomial time. It is also known that the planar Maximum Bisection is NP-hard in exact setting and it admits a PTAS.

What is the computational status of Minimum Bisection on planar graphs? Is it NP-hard? Does it admit a constant factor approximation (or even a PTAS similarly to planar Maximum Bisection)?