# A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs

Preprint · Debarati Das, Evangelos Kipouridis, Maximilian Probst Gutenberg, Christian Wulff-Nilsen

- Archive id: arxiv:2111.07360
- Published: 2021-11-14
- arXiv: https://arxiv.org/abs/2111.07360
- Source URL: https://arxiv.org/abs/2111.07360
- PDF: https://arxiv.org/pdf/2111.07360
- Provenance: arxiv

## Abstract

Given an $n$-vertex planar embedded digraph $G$ with non-negative edge weights and a face $f$ of $G$, Klein presented a data structure with $O(n\\log n)$ space and preprocessing time which can answer any query $(u,v)$ for the shortest path distance in $G$ from $u$ to $v$ or from $v$ to $u$ in $O(\\log n)$ time, provided $u$ is on $f$. This data structure is a key tool in a number of state-of-the-art algorithms and data structures for planar graphs. Klein's data structure relies on dynamic trees and the persistence technique as well as a highly non-trivial interaction between primal shortest path trees and their duals. The construction of our data structure follows a completely different and in our opinion very simple divide-and-conquer approach that solely relies on Single-Source Shortest Path computations and contractions in the primal graph. Our space and preprocessing time bound is $O(n\\log \|f\|)$ and query time is $O(\\log \|f\|)$ which is an improvement over Klein's data structure when $f$ has small size.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
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 Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.