Multiple-Source Shortest Paths in Embedded Graphs

Abstract

Let $G$ be a directed graph with $n$ vertices and nonnegative weights in its directed edges, embedded on a surface of genus $g$, and let $f$ be an arbitrary face of $G$. We describe a randomized algorithm to preprocess the graph in $O(gn \log n)$ time with high probability, so that the shortest-path distance from any vertex on the boundary of $f$ to any other vertex in $G$ can be retrieved in $O(\log n)$ time. Our result directly generalizes the $O(n\log n)$-time algorithm of Klein [Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 2005] for multiple-source shortest paths in planar graphs. Intuitively, our preprocessing algorithm maintains a shortest-path tree as its source point moves continuously around the boundary of $f$. As an application of our algorithm, we describe algorithms to compute a shortest noncontractible or nonseparating cycle in embedded, undirected graphs in $O(g^2 n\log n)$ time with high probability. Our high-probability time bounds hold in the worst case for generic edge weights or with an additional $O(\log n)$ factor for arbitrary edge weights.