Multiple-Source Shortest Paths in Embedded Graphs

Abstract

Let G be a directed graph with n vertices and non-negative 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 [SODA 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 non-contractible or non-separating 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.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.