# Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time

Preprint · Lorenzo Balzotti, Paolo G. Franciosa

- Archive id: arxiv:2102.10892
- Published: 2021-02-22
- Venue: Journal of Graph Algorithms and Applications, Vol. 26, no. 4, pp. 589-606, 2022
- DOI: https://doi.org/10.7155/jgaa.00610
- arXiv: https://arxiv.org/abs/2102.10892
- Source URL: https://arxiv.org/abs/2102.10892
- PDF: https://arxiv.org/pdf/2102.10892
- Provenance: arxiv

## Abstract

Given a set of well-formed terminal pairs on the external face of an undirected planar graph with unit edge weights, we give a linear-time algorithm for computing the union of non-crossing shortest paths joining each terminal pair, where well-formed means that such a set of non-crossing paths exists. This allows us to compute distances between each terminal pair, within the same time bound. We also give a novel concept of incremental shortest path subgraph of a planar graph, i.e., a partition of the planar embedding in subregions that preserve distances, that can be of interest itself.

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