# What is the Complexity Status of Arbitarily Weighted Planar Max Cut?

If you search on the internet for the Complexity Status of Arbitarily Weighted Planar Max Cut you seem to get conflicting answers.

On one hand, there are references that Barahona solved this problem in the 1980's.

On the other there is this paper: NP-completeness of maximum-cut and cycle-covering problems for planar graphs

My question is what is the Complexity Status of Arbitarily Weighted Planar Max Cut?

• Planar Max-Cut reduces to computing a min-cost T-join in the dual graph which in turn reduces to computing a min-cost perfect matching. This was first shown by Hadlock in 1975. The paper is available here. web.eecs.umich.edu/~pettie/matching/… Jun 22 at 22:26

Arbitarily Weighted Planar Max Cut is polynomialy solvable. Shih, Wu, and Kuo provided a polynomial time algorithm with run-time of $O(n^{3/2} \log n)$.