Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs.

David Eisenstat, Philip N. Klein

Browse the full STOC paper archive.