Reif's Minimum Cut Algorithm

Purpose: Compute the minimum cut of an undirected planar graph in $O(n{\log }^{2}n)$ (later improved to $O(n\log \log n)$) by exploiting planar duality — much faster than any general min-cut algorithm.

The Duality

For a planar graph $G$ embedded in the plane, build the dual $G^{\ast }$: one vertex per face, one edge per edge of $G$ connecting the two faces it separates, with the same weight.

Key correspondence: cuts in $G$ ↔ cycles in $G^{\ast }$.

A minimal edge set whose removal disconnects $G$ corresponds exactly to a closed curve in the plane, i.e. a cycle in the dual.

Therefore:

$\text{minimum cut in }G=\text{minimum weight cycle in }{G}^{\ast }.$

And the minimum weight cycle in a planar graph can be found by shortest-path techniques rather than flow.

Algorithm sketch

1. Build the planar embedding and the dual graph.
2. Finding a minimum-weight cycle in the dual reduces to a set of shortest-path computations. Reif uses a divide and conquer on a planar separator: the planar separator theorem gives a set of $O(\sqrt{n})$ vertices whose removal splits the graph into balanced halves. Any minimum cycle either avoids the separator (recurse) or crosses it (handle with shortest paths from separator vertices).
3. Recursion depth $O(\log n)$, each level $O(n\log n)$, total $O(n{\log }^{2}n)$.

Later work (Chalermsook-Fakcharoenphol-Nanongkai, Italiano et al.) brought this to $O(n\log \log n)$ using more refined divide and conquer over the dual.

Complexity

Graph class	Min cut
General	$O(nm+n^2\log n)$ (Stoer-Wagner)
General, randomized	$O(m{\log }^{3}n)$ (Karger)
Planar, undirected	$O(n\log \log n)$
Planar, $s$-$t$ max flow	$O(n\log n)$ (Borradaile-Klein)

Planar duality more broadly

This is one instance of a very productive pattern:

Primal (in $G$)	Dual (in $G^{\ast }$)
cut	cycle
$s$-$t$ min cut	shortest path between two specific faces
spanning tree	complement is a spanning tree of the dual
max flow	shortest-path / “uppermost path” structure
face	vertex

The $s$-$t$ version is especially useful: an $s$-$t$ min cut in a planar graph becomes a shortest path in a modified dual, solvable with Dijkstra in $O(n\log n)$ instead of running max flow. Grid problems where you must “cut a path from left to right” are exactly this, and contest problems do use it.

Variants / Use Cases

• Grid cutting problems — “block every path from top to bottom at minimum cost” is an $s$-$t$ planar min cut, hence a shortest path in the dual grid
• Minimum Cut and Global Min Cut — the topic pages
• Stoer-Wagner — the general-graph algorithm
• Image segmentation — planar min cut on a pixel grid; the original application of graph cuts in vision