Tech Report CS-94-12

Faster Shortest-Path Algorithms for Planar Graphs

Philip Klein, Satish Rao, Monika Rauch, and Sairam Subramanian

March 1994

Abstract:

We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph with the source and sink on the same face. The previous best algorithms for these problems required $\Omega(n \sqrt{\log n})$ time where $n$ is the number of nodes in the input graph.

For the case where negative edge-lengths are allowed, we give an algorithm requiring $O(n^{4/3} \log nL)$ time, where $L$ is the absolute value of the most negative length. Previous algorithms for shortest paths with negative edge-lengths required $\Omega(n^{3/2})$ time. Our shortest-path algorithm yields an $O(n^{4/3} \log n)$-time algorithm for finding a perfect matching in a planar bipartite graph. A similar improvement is obtained for maximum flow in a directed planar graph.

(complete text in pdf or gzipped postscript)