# 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 http://www.springerlink.com/content/xj7238374871347j/

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

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)$.