Unifying maximum cut and minimum cut of a planar graph

Abstract

The real-weight maximum cut of a planar graph is considered. Given an undirected planar graph with real-value weights associated with its edges, the problem is to find a partition of the vertices into two nonempty sets such that the sum of the weights of the edges connecting the two sets is maximum. The conventional maximum cut and minimum cut problems assume nonnegative edge weights, and thus are special cases of the real-weight maximum cut. An O(n/sup 3/2/ log n) algorithm for finding a real-weight maximum cut of a planar graph where n is the number of vertices in the graph is developed. The best maximum cut algorithm previously known for planar graphs has running time of O(n/sup 3/).< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>