Glencora Borradaile

Glencora Borradaile, Piotr Sankowski and Christian Wulff-Nilsen

For an undirected n-vertex planar graph G with non-negative edge-weights, we consider the following type of query: given two vertices s and t in G, what is the weight of a min st-cut in G? We show how to answer such queries in constant time with O(n log⁵ n) preprocessing time and O(n log n) space. We use a Gomory-Hu tree to represent all the pairwise min cuts implicitly. Previously, no subquadratic time algorithm was known for this problem. Since all-pairs min cut and the minimum cycle basis are dual problems in planar graphs, we also obtain an implicit representation of a minimum cycle basis in O(n log⁵n) time and O(n log n) space and an explicit representation with additional O(C) time and space where C is the size of the basis. These results require that shortest paths be unique. We deterministically remove this assumption with an additional log²n factor in the running time.

To appear at FOCS 2010.

[ arXiv ]

Filed under: Conference, Publications by Glencora