# Improved Bounds for Shortest Paths in Dense Distance Graphs

Article · Paweł Gawrychowski, Adam Karczmarz

- Archive id: arxiv:1602.07013
- Published: 2016-02-23
- DOI: https://doi.org/10.4230/lipics.icalp.2018.61
- arXiv: https://arxiv.org/abs/1602.07013
- Citations: 13
- Source URL: https://arxiv.org/abs/1602.07013
- PDF: https://arxiv.org/pdf/1602.07013
- Provenance: arxiv

## 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 reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.