Duality
Add edge from t to s. Dual graph: face-adjacency. Shortest cycle through the new edge in dual = min cut = max flow.
Advertisement
Directed planar
More subtle. Fast algorithms exist: O(V log² V) or better.
Advertisement
Multi-source planar
Miller-Naor: O(V log³ V) all-pairs flow via multiple s-t reductions.
Applications
Circuit design (planar). Image segmentation (planar grid). Road networks (approximately planar).