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 lengths 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$. This technique only applies when the union $U$ of the computed shortest paths is a forest. 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 $\pi$ can be listed in $O(\ell+\ell\log\lceil{\frac{k}{\ell}}\rceil)$, where $\ell$ is the number of edges in $\pi$. As a consequence, the problem of computing multi-terminal distances in a plane undirected weighted graph can always be solved in $O(n \log k)$ worst-case time in the general case.