Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00610
Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
Vol. 26, no. 4, pp. 589-606, 2022. Regular paper.
Abstract Given a set of terminal pairs on the external face of an undirected unweighted planar graph, we give a linear-time algorithm for computing the union of non-crossing shortest paths joining each terminal pair, if such paths exist. 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.
 This work is licensed under the terms of the CC-BY license.
Submitted: July 2022.
Reviewed: October 2022.
Revised: October 2022.
Accepted: December 2022.
Final: December 2022.
Published: December 2022.
Communicated by Giuseppe Liotta
article (PDF)
BibTeX