The planar multiterminal cut problem
David Hartvigsen · Discrete Applied Mathematics · 1998
Let G = (V, E) be a graph with positive edge weights and let V'⊆V. The min V1-cut problem is to find a minimum weight set E'⊆E such that no two nodes of V' occur in the same component of G' = (V, EE'). Our main results are two new structural theorems for optimal solutions to the min V'-cut problem when G is planar. The first theorem establishes for the first time a close connection between the planar min V'-cut problem and the well-known “Gomory-Hu” cut collections. The second theorem establishes a connection between the planar min V'-cut problem and a particular matroid. Each theorem results in a simple algorithm for the planar min V'-cut problem. The first algorithm is based upon the most efficient previous algorithm for this problem (due to Dahlhaus et al.) and achieves a lower time complexity.