The All-Pairs Min Cut Problem and the Minimum Cycle Basis Problem on Planar Graphs

Abstract

The all-pairs min cut (APMC) problem on a nonnegative weighted graph is the problem of finding, for every pair of nodes, the min cut separating the pair. It is shown that on planar graphs, the APMC problem is equivalent to another problem, the minimum cycle basis (MCB)problem, on the dual graph. This is shown by characterizing the structure of MCBs on planar graphs in several ways. This leads to a new algorithm for solving both of these problems on planar graphs. The complexity of this algorithm equals that of the best algorithm for either problem, but is simpler.