Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


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(nlog^5n)$ 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(nlog^5n)$ time and $O(nlog 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^2 n$ factor in the running time.

Questions and Answers

You need to be logged in to be able to post here.