## A deterministic near-linear time algorithm for ﬁnding minimum cuts in planar graphs (SODA’04)

We present a simple deterministic O(n log2
n)-time divide-
and-conquer algorithm for ﬁnding minimum cuts in planar
graphs. This can be compared to a randomized algorithm
for general graphs by Karger that runs in time O(mlog3
n)
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 ﬁnd

minimum cuts that cross the partitions eﬃciently.Au

Journal:

Conference: SODA 2004 (Short paper): 15th Annual ACM-SIAM Symposium on Discrete Algorithms [link]

Abstract:

We present a simple deterministic $O(n(\log n)^2)$-time divide-and-conquer algorithm for ﬁnding minimum cuts in planar graphs. This can be compared to a randomized algorithm for general graphs by Karger that runs in time $O(m(\log n)^3)$ and also a deterministic algorithm for general graphs by Nagamochi and Ibaraki that runs in time $O(mn+n^2 \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 ﬁnd minimum cuts that cross the partitions eﬃciently.

Update history:
[v1]: January 2004