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) worst-case time, where n is the number of vertices of G. If the union U of the computed shortest paths is a forest, it is also shown that their lengths can be computed in the same time bound O(n log n). We show that given a plane undirected weighted graph U and a set of k terminal pairs on the external face, it is always possible to compute the lengths of k non-crossing shortest paths joining the k terminal pairs in linear worst-case time, provided that the graph U is the union of k shortest paths, possibly containing cycles. Moreover, each shortest path π can be listed in O(l+llog⌈k⌉), where l is the number of edges in π. l As a consequence, the problem of computing multi-terminal distances in a plane undirected weighted graph can be solved in O(n log k) worst-case time in the general case.

Computing Lengths of Shortest Non-Crossing Paths in Planar Graphs / Balzotti, Lorenzo; And, ; Franciosa, Paolo Giulio. - (2020).

Computing Lengths of Shortest Non-Crossing Paths in Planar Graphs

Lorenzo Balzotti
;
Paolo Giulio Franciosa
2020

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) worst-case time, where n is the number of vertices of G. If the union U of the computed shortest paths is a forest, it is also shown that their lengths can be computed in the same time bound O(n log n). We show that given a plane undirected weighted graph U and a set of k terminal pairs on the external face, it is always possible to compute the lengths of k non-crossing shortest paths joining the k terminal pairs in linear worst-case time, provided that the graph U is the union of k shortest paths, possibly containing cycles. Moreover, each shortest path π can be listed in O(l+llog⌈k⌉), where l is the number of edges in π. l As a consequence, the problem of computing multi-terminal distances in a plane undirected weighted graph can be solved in O(n log k) worst-case time in the general case.
2020
2331-8422
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1501676
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact