View article

We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edgelengths. 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! J (n=) time where n is the number of nodes in the input graph, For the case where negattve edge-lengths are a!-iowed, we gave an algorzthm requiring 0 (n4/3 log nL) time, where L is the absolute value of the most negative length. Previous algorithms for shortest paths with negative edge-lengths requzred Q (n3/2) time. Our shortest-path algorithm ytelds an 0 (n413 log n)-tame algorithm for jinding a perfect matching in a pianar bipartite graph. A similar improvement is obtained for maximum jlow in a directed planar graph.