Min-cuts and Shortest Cycles in Planar Graphs in O(n log log n) Time

Jakub Łącki, Piotr Sankowski

We present a deterministic O(n log log n) time algorithm for finding shortest cycles and minimum cuts in planar graphs. The algorithm improves the previously known fastest algorith…