Faster shortest-path algorithms for planar graphs

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. 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. This algorithm can be used to obtain similar bounds for computing a feasible flow in a planar network, for finding a perfect matching in a planar bi partite graph, a nd for finding a maxim um flow in a planar graph when the source and sink are not on the same face. We also give parallel and dynamic versions of these algorithms. (C) 1997 Academic Press.