Minimums-tCut of a Planar Undirected Network in O(nlog ² (n)) Time

Let N be a planar undirected network with distinguished vertices s, t, a total of n vertices, and each edge labeled with a positive real (the edge’s cost) from a set L. This paper presents an algorithm for computing a minimum (cost) s-t cut of N. For general L, this algorithm runs in time O(nlog ² (n)). For the case when L contains only integersnO(1), the algorithm runs in time O(nlog (n)log log (n)). Our algorithm also constructs a minimum s-t cut of a planar graph (i.e., for the case L = \ 1\) in time O(nlog (n)). Our algorithm can also be used to compute a minimum cut for a general undirected planar network. The fastest previous algorithm for computing a minimum s-t cut of a planar undirected network (Itai and Shiloach [SIAM J. Comput., 8 (1979), pp. 135–150]) has time O(n² log (n)); the s-t cut is a byproduct of the maximum flow computed by their algorithm. The best previous time bound for minimum s-t cut of a planar graph (Cheston, Probert and Saxton [report, Dept. Computer Science, Univ. Saskatchewan, 1977]) was O(n² ).