Multiple source shortest paths in a genus g graph
Sergio Cabello, Erin Wolf Chambers · 2007
We give an O(g2n log n) algorithm to represent the shortest path tree from all the vertices on a single specified face f in a genus g graph. From this representation, any query distance from a vertex in f can be obtained in O(log n) time. The algorithm uses a kinetic data structure, where the source of the tree iteratively movesacrossedgesinf. In addition, we give applications using these shortest path trees in order to compute the shortest non-contractible cycle and the shortest nonseparating cycle embedded on an orientable 2-manifold in O(g3n log n) time. 1