Fast algorithms for shortest paths in planar graphs, with applications. (English) Zbl 0654.68087

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 \(\sqrt{\log n})\) time in an n-vertex graph, an improvement from O(n log n). The algorithm for all pairs takes \(O(n^ 2)\) time, an improvement from \(O(n^ 2 \log n)\). The algorithm for minimum cut takes O(n log n) time, an improvement from O(n (log n)\({}^ 2)\). As a consequence, an algorithm for maximum flow is similarly improved.


68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
05C38 Paths and cycles
68P05 Data structures
Full Text: DOI Link