Faster shortest paths in dense distance graphs, with applications.

We show how to combine two techniques for efficiently computing shortest paths in directed planar graphs. The first is the linear-time shortest-path algorithm of Henzinger, Klein, Subramanian, and Rao [STOC'94]. The second is Fakcharoenphol and Rao's algorithm [FOCS'01] for emulating Dijkstra's algorithm on the dense distance graph (DDG). A DDG is defined for a decomposition of a planar graph G into regions of at most r vertices each, for some parameter r < n . The vertex set of the DDG is the set of Θ ( n r − 1 / 2 ) vertices of G that belong to more than one region (boundary vertices). The DDG has Θ ( n ) arcs, such that distances in the DDG are equal to the distances in G . Fakcharoenphol and Rao's implementation of Dijkstra's algorithm on the DDG (nicknamed FR-Dijkstra ) runs in O ( n log ⁡ ( n ) r − 1 / 2 log ⁡ r ) time, and is a key component in many state-of-the-art planar graph algorithms for shortest paths, minimum cuts, and maximum flows. By combining these two techniques we remove the log ⁡ n dependency in the running time of the shortest-path algorithm at the price of an additional log ⁡ r factor, making it O ( n r − 1 / 2 log 2 ⁡ r ) . This work is part of a research agenda that aims to develop new techniques that would lead to faster, possibly linear-time, algorithms for problems in planar graphs such as minimum-cut, maximum-flow, and shortest paths with negative arc lengths. As immediate applications, we show how to compute maximum flow in directed weighted planar graphs in O ( n log ⁡ p ) time, and minimum st -cut in undirected weighted planar graphs in O ( n log ⁡ log ⁡ p ) time, where p is the minimum number of edges on any path from the source to the sink. We also show how to compute any part of the DDG that corresponds to a region with r vertices and k boundary vertices in O ( r log ⁡ k ) time, which is faster than has been previously known for small values of k . [ABSTRACT FROM AUTHOR]