Min st-cuts in planar graphs

Christian Wulff-Nilsen

Given a graph G = (V,E) with non-negative edge weights and given two vertices s and t in G, an st-cut in G is a partition of V into subsets S and T = V\S such that s is in S and t is in T. The weight of the st-cut is the sum of weights of edges starting in S and ending in T. A min st-cut is an st-cut of minimum weight.

We consider the min st-cut problem for planar undirected graphs. Our first result is an O(n loglog n) time algorithm for the problem, where n is the size of the graph. This is an improvement of an earlier bound of O(n log n) (Frederickson, 1987). Our second result (joint work with Glencora Borradaile and Piotr Sankowski, to be presented at FOCS 2010) is an oracle for answering min st-cut weight queries after O(n polylog n) preprocessing time. The previous best preprocessing bound was O(n2) (Amaldi et al., 2009). Our oracle can be extended to report the min st-cuts in time proportional to their size.