Multiple-source shortest paths in embedded graphs

Sergio Cabello, Erin W. Chambers, Jeff Erickson

Research output: Contribution to journalArticlepeer-review

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(g2n 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.

Original languageEnglish (US)
Pages (from-to)1542-1571
Number of pages30
JournalSIAM Journal on Computing
Volume42
Issue number4
DOIs
StatePublished - 2013

Keywords

  • Computational topology
  • Dynamic data structures
  • Parametric shortest paths
  • Topological graph theory

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Multiple-source shortest paths in embedded graphs'. Together they form a unique fingerprint.

Cite this