Status of Minimum Bisection on Planar Graphs

From himtp
Revision as of 11:29, 23 November 2015 by Karpinski (Talk | contribs) (initial version)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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)?