1994/01/01 by Philip N. Klein, Satish Rao, Monika Rauch +1 · 114 citations
Computer Science · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Optimization and Search Problems #Citation #Computer science #Algorithm #Path (computing) #Planar graph #Shortest path problem #Theoretical computer science #Graph #Library science #Programming language
paper · doi:10.1145/195058.195092
openalex publication_date 1994/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08
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\Ω\Γ n p 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 \Ω\Γ 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.