Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
Greg N. Federickson · SIAM Journal on Computing · 1987
Graph decomposition and data structures techniques are presented that exploit the structure of planar graphs to yield faster algorithms for a number of shortest path and related problems. Improved algorithms are presented for the single source problem, the all pairs problem, the problem of finding a minimum cut in an undirected graph, and testing the feasibility of a multicommodity flow when all sources and sinks are on the same face. The algorithm for the single source takes $O(n\sqrt {\log n} )$ time in an n-vertex graph, an improvement from $O(n\log n)$. The algorithm for all pairs takes $O(n^2 )$ time, an improvement from $O(n^2 \log n)$. The algorithm for minimum cut takes $O(n\log n)$ time, an improvement from $O(n(\log n)^2 )$. As a consequence, an algorithm for maximum flow is similarly improved.