# Simple analysis of an algorithm for multiple-source shortest paths in planar graphs

Preprint · Philip N. Klein

- Archive id: arxiv:2610.02371
- Published: 2026-10-01
- arXiv: https://arxiv.org/abs/2610.02371
- Source URL: https://arxiv.org/abs/2610.02371
- PDF: https://arxiv.org/pdf/2610.02371
- Provenance: arxiv

## Abstract

This paper addresses the following problem: given a planar embedding graph, compute a representation of the shortest-path trees rooted at all the boundary nodes of the graph. Klein gave an $O(n \\log n)$ algorithm for this problem; the algorithm subsequently became an essential ingredient in dozens of algorithms, addressing problems ranging from distance oracles to edit distance. However, the correctness and analysis in that original paper is complicated and messy and hard to understand. In this paper, we give a simple and clear analysis.

_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.