Minimum Cut of Directed Planar Graphs in O(nloglogn) Time

Abstract

We give an $O(n\log \log n)$ time algorithm for computing the minimum cut (or equivalently, the shortest cycle) of a weighted directed planar graph. This improves the previous fastest $O(n{\log }^{3}n)$ solution. Interestingly, while in undirected planar graphs both min-cut and min $st$-cut have $O(n\log \log n)$ solutions, in directed planar graphs our result makes min-cut faster than min $st$-cut, which currently requires $O(n\log n)$.

References in corpus (3)

• Computing the Girth of a Planar Graph in Linear Time
• Multiple-Source Shortest Paths in Embedded Graphs
• Girth of a Planar Digraph with Real Edge Weights in O(n(log n)^3) Time

Cited by in corpus (1)

• Topologically Trivial Closed Walks in Directed Surface Graphs