Multiple source shortest paths in a genus g graph

ABSTRACT

We give an O(g²nlog 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(g³nlog n) time.

REFERENCES

• 1: S. Cabello and B. Mohar. Finding shortest non-separating and non-contractible cycles for topologically embedded graphs. In G. S. Brodal and S Leonardi, editors, Algorithms--ESA 2005, 13th Annual European Symposium, Palma de Mallorca, Spain, October 3--6, 2005, Proceedings, volume 3669 of LNCS, pages 131--142. Springer, 2005.
• 2: Erin W. Chambers , Éric Colin de Verdière , Jeff Erickson , Francis Lazarus , Kim Whittlesey, Splitting (complicated) surfaces is hard, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137918]
• 3: Éric Colin de Verdière , Jeff Erickson, Tightening non-simple paths and cycles on surfaces, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.192-201, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109580]
• 4: J R Driscoll , N Sarnak , D D Sleator , R E Tarjan, Making data structures persistent, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.109-121, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12142]
• 5: J. Erickson and S. Har-Peled. Optimally cutting a surface into a disk. Discrete and Comput. Geometry, 31(1):37--59, 2004.
• 6: Greg N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM Journal on Computing, v.16 n.6, p.1004-1022, December 1, 1987 [doi>10.1137/0216064]
• 7: L. Guibas. Kinetic data structures: A state of the art report, 1998.
• 8: Monika R. Henzinger , Valerie King, Randomized fully dynamic graph algorithms with polylogarithmic time per operation, Journal of the ACM (JACM), v.46 n.4, p.502-516, July 1999 [doi>10.1145/320211.320215]
• 9: Philip N. Klein, Multiple-source shortest paths in planar graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 10: Martin Kutz, Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137919]
• 11: R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM J. Appl. Math., 36:177--189, 1979.
• 12: K. Mulmuley , U. V. Vazirani , V. V. Vazirani, Matching is as easy as matrix inversion, Combinatorica, v.7 n.1, p.105-113, Jan. 1987 [doi>10.1007/BF02579206]
• 13: Jeanette P. Schmidt, All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings, SIAM Journal on Computing, v.27 n.4, p.972-992, Aug. 1998 [doi>10.1137/S0097539795288489]
• 14: J. Stillwell. Classical Topology and Combinatorial Group Theory. Springer-Verlag, New York, 1993.
• 15: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 16: Robert E. Tarjan , Renato F. Werneck, Self-adjusting top trees, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 17: Afra J. Zomorodian , M. J. Ablowitz , S. H. Davis , E. J. Hinch , A. Iserles , J. Ockendon , P. J. Olver, Topology for Computing (Cambridge Monographs on Applied and Computational Mathematics), Cambridge University Press, New York, NY, 2005