Improved bounds for shortest paths in dense distance graphs

We study the problem of computing shortest paths in so-called dense distance graphs, a basic building block for designing efficient planar graph algorithms. Let G be a plane graph with a distinguished set partial{G} of boundary vertices lying on a constant number of faces of G. A distance clique of G is a complete graph on partial{G} encoding all-pairs distances between these vertices. A dense distance graph is a union of possibly many unrelated distance cliques. Fakcharoenphol and Rao [Fakcharoenphol and Rao, 2006] proposed an efficient implementation of Dijkstra's algorithm (later called FR-Dijkstra) computing single-source shortest paths in a dense distance graph. Their algorithm spends O(b log^2{n}) time per distance clique with b vertices, even though a clique has b^2 edges. Here, n is the total number of vertices of the dense distance graph. The invention of FR-Dijkstra was instrumental in obtaining such results for planar graphs as nearly-linear time algorithms for multiple-source-multiple-sink maximum flow and dynamic distance oracles with sublinear update and query bounds. At the heart of FR-Dijkstra lies a data structure updating distance labels and extracting minimum labeled vertices in O(log^2{n}) amortized time per vertex. We show an improved data structure with O((log^2{n})/(log^2 log n)) amortized bounds. This is the first improvement over the data structure of Fakcharoenphol and Rao in more than 15 years. It yields improved bounds for all problems on planar graphs, for which computing shortest paths in dense distance graphs is currently a bottleneck.