Faster shortest paths in dense distance graphs, with applications

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(nlog⁡p) time, and minimum st-cut in undirected weighted planar graphs in O(nlog⁡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(rlog⁡k) time, which is faster than has been previously known for small values of k.