Shortest non-trivial cycles in directed surface graphs

Proceedings of the 27th Annual Symposium on Computational Geometry, 236–243, 2011.


Abstract:
Let G be a directed graph embedded on a surface of genus g. We describe an algorithm to compute the shortest non-separating cycle in G in O(g2n log n) time, exactly matching the fastest algorithm known for undirected graphs. We also describe an algorithm to compute the shortest non-contractible cycle in G in gO(g)n log n time, matching the fastest algorithm for undirected graphs of constant genus.


Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 30 Mar 2012