Finding shortest non-trivial cycles in directed graphs on surfaces
Finding shortest non-trivial cycles in directed graphs on surfaces
Let D be a weighted directed graph cellularly embedded in a surface of genus g, orientable or not, possibly with boundary. We describe algorithms to compute a shortest non-contractible and a shortest surface non-separating cycle in D. This generalizes previous results that only dealt with undirected graphs.