# Complexity of Max Bisection on cubic planar graphs?

Max Bisection problem is to partition the set of nodes into two equal size sets such that the number of crossing edges is maximized. Max Bisection is $NP$-complete on cubic graphs and also on planar graphs.

What is the complexity of Max Bisection on cubic planar graphs? Is it $NP$-complete?

Cross posted on SE tcs

-

I am pretty sure that the result in http://rutcor.rutgers.edu/pub/rrr/reports2006/23_2006.pdf tells us that Max-Bisection is NP-hard on bounded degree planar graphs (however, I think the bound is bigger than three) -- you would have to chase down their construction to be sure.

-