al Scien..f' : FOl~"C'l1jon nnrkr G:J'1'nr~MCS-8201083 and DCR-83Z0124. Abstract. 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 multicomrnodity flow when all sources and sinks are on the same face. The algorithm for the single source takes 0 (n ...' 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 0 (n 2 log n). The algorithm for minimum cut takes 0 (n log n) time, an improvement from 0 (n (log n )2). As a consequence, an algorithm for maximum flow is similarly improved.
Frederickson REF proposed a hierarchical algorithm for the single-source shortest path problem on planar graphs.
Fast algorithms for shortest paths in planar graphs, with applications
SIAM J. Comput.
SIAM J. Comput.
Mathematics Computer Science