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(g^{2}n 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 g^{O(g)}n log n time, matching the fastest algorithm for undirected graphs of constant genus.