1997/08/01 by Monika Henzinger, Philip N. Klein, Satish Rao +1 · 6 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Planar graph #Bipartite graph #Planar straight-line graph #Shortest path problem #Algorithm #Mathematics #Maximum flow problem #Combinatorics #Planar #Outerplanar graph #Suurballe's algorithm #Shortest Path Faster Algorithm #Time complexity #Matching (statistics) #Discrete mathematics #Computer science #Graph #Line graph #K shortest path routing #Pathwidth #Dijkstra's algorithm
paper · doi:10.1006/jcss.1997.1493
openalex publication_date 1997/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/23
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 requiringO(n4/3 log(nL)) time, whereLis 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 bipartite graph, and for finding a maximum 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.