2016/02/23 by Gawrychowski, Paweł, Karczmarz, Adam
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1602.07013
We study the problem of computing shortest paths in so-called dense distance graphs. Every planar graph G on n vertices can be partitioned into a set of O(n/r) edge-disjoint regions (called an r-division) with O(r) vertices each, such that each region has O(√(r)) vertices (called boundary vertices) in common with other regions. A dense distance graph of a region is a complete graph containing all-pairs distances between its boundary nodes. A dense distance graph of an r-division is the union of the O(n/r) dense distance graphs of the individual pieces. Since the introduction of dense distance graphs by Fakcharoenphol and Rao, computing single-source shortest paths in dense distance graphs has found numerous applications in fundamental planar graph algorithms. Fakcharoenphol and Rao proposed an algorithm (later called FR-Dijkstra) for computing single-source shortest paths in a dense distance graph in O((n)/(√(r))lognlogr) time. We show an O((n)/(√(r))(\fraclog2rlog2logr+lognlogεr)) time algorithm for this problem, which is the first improvement to date over FR-Dijkstra for the important case when r is polynomial in n. In this case, our algorithm is faster by a factor of O(log2logn) and implies improved upper bounds for such planar graph problems as multiple-source multiple-sink maximum flow, single-source all-sinks maximum flow, and (dynamic) exact distance oracles.