Shortest non-trivial cycles in directed surface graphs
Jeff Erickson · 2011
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(g2 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 gO(g)n log n time, matching the fastest algorithm for undirected graphs of constant genus.