1987/12/01 by Greg N. Federickson · 444 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Combinatorics #Mathematics #Shortest path problem #Binary logarithm #Algorithm #Time complexity #Maximum flow problem #Vertex (graph theory) #Graph algorithms #Planar graph #Graph #Undirected graph #Discrete mathematics
paper · doi:10.1137/0216064
published in SIAM Journal on Computing 16(6), 1004-1022 (Society for Industrial and Applied Mathematics)
openalex publication_date 1987/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
Graph decomposition and data structures techniques are presented that exploit the structure of planar graphs to yield faster algorithms for a number of shortest path and related problems. Improved algorithms are presented for the single source problem, the all pairs problem, the problem of finding a minimum cut in an undirected graph, and testing the feasibility of a multicommodity flow when all sources and sinks are on the same face. The algorithm for the single source takes O(n√ log n ) time in an n-vertex graph, an improvement from O(nlog n). The algorithm for all pairs takes O(n2 ) time, an improvement from O(n2 log n). The algorithm for minimum cut takes O(nlog n) time, an improvement from O(n(log n)2 ). As a consequence, an algorithm for maximum flow is similarly improved.