Maximum Cut Algorithms and Upper Bounds for Planar and Toroidal Graphs

Mark Glass, Meir Feder

We demonstrate that the problem of finding the maximum cut of a planar graph with arbitrary weights can be easily mapped to a minimum T-join problem in the absolute dual graph - th…