# Computing Lengths of Non-Crossing Shortest Paths in Planar Graphs

Preprint · Lorenzo Balzotti, Paolo G. Franciosa

- Archive id: arxiv:2011.04047
- Published: 2020-11-08
- Venue: Algorithms and Complexity 13th International Conference, CIAC 2023
- DOI: https://doi.org/10.1007/978-3-031-30448-4_6
- arXiv: https://arxiv.org/abs/2011.04047
- Citations: 0
- Source URL: https://arxiv.org/abs/2011.04047
- PDF: https://arxiv.org/pdf/2011.04047
- Provenance: arxiv

## Abstract

Given a plane undirected graph $G$ with non-negative edge weights and a set of $k$ terminal pairs on the external face, it is shown in Takahashi et al. (Algorithmica, 16, 1996, pp. 339-357) that the union $U$ of $k$ non-crossing shortest paths joining the $k$ terminal pairs (if they exist) can be computed in $O(n\\log n)$ time, where $n$ is the number of vertices of $G$. In the restricted case in which the union $U$ of the shortest paths is a forest, it is also shown that their lengths can be computed in the same time bound. We show in this paper that it is always possible to compute the lengths of $k$ non-crossing shortest paths joining the $k$ terminal pairs in linear time, once the shortest paths union $U$ has been computed, also in the case $U$ contains cycles. Moreover, each shortest path $π$ can be listed in $O(\\max\\{\\ell, \\ell \\log\\frac{k}{\\ell} \\})$, where $\\ell$ is the number of edges in $π$. As a consequence, the problem of computing non-crossing shortest paths and their lengths in a plane undirected weighted graph can be solved in $O(n\\log k)$ time in the general case.

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