Multiple source shortest paths in a genus g graph

Abstract

We give an O(g2nlog 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 moves across edges in f. In addition, we give applications using these shortest path trees in order to compute the shortest non-contractible cycle and the shortest non-separating cycle embedded on an orientable 2-manifold in O(g3nlog n) time.