A deterministic near-linear time algorithm for finding minimum cuts in planar graphs
Parinya Chalermsook, Jittat Fakcharoenphol, Danupon Nanongkai · Symposium on Discrete Algorithms · 2004
We present a simple deterministic O(n log2n)-time divide-and-conquer algorithm for finding minimum cuts in planar graphs. This can be compared to a randomized algorithm for general graphs by Karger that runs in time O(m log3n) and also a deterministic algorithm for general graphs by Nagamochi and Ibaraki that runs in time O(mn + n2 log n). We use shortest paths in the dual graphs to partition the problem, and use the relationship between minimum cuts in primal graphs and shortest paths in dual graphs to find minimum cuts that cross the partitions efficiently.