2010/03/05 by Glencora Borradaile, Borradaile, Glencora, Piotr Sankowski +3 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2.2
paper · pdf · doi:10.48550/arxiv.1003.1320
openalex publication_date 2010/03/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(nlog4n) preprocessing time and O(nlog 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(nlog4n) time and O(nlog n) space. Additionally, an explicit representation can be obtained in O(C) time and space where C is the size of the basis. These results require that shortest paths are unique. This can be guaranteed either by using randomization without overhead, or deterministically with an additional log2 n factor in the preprocessing times.