Computing Lengths of Shortest Non-Crossing Paths in Planar Graphs

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.