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.
Non-crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time / Balzotti, Lorenzo; Franciosa, Paolo G.. - 13296 LNCS:(2022), pp. 77-95. ((Intervento presentato al convegno Computer science - theory and applications - 17th international computer science symposium in Russia, {CSR} 2022 tenutosi a Russia [10.1007/978-3-031-09574-0_6].
Non-crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
Lorenzo Balzotti
Membro del Collaboration Group
;Paolo G. FranciosaMembro del Collaboration Group
2022
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
