Improved Bounds for Shortest Paths in Dense Distance Graphs

Abstract

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(\sqrt{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\left(\frac{n}{\sqrt{r}}\log{n}\log{r}\right)$ time. We show an $O\left(\frac{n}{\sqrt{r}}\left(\frac{\log^2{r}}{\log^2\log{r}}+\log{n}\log^ε{r}\right)\right)$ 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(\log^2{\log{n}})$ 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.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.