Topologically Trivial Closed Walks in Directed Surface Graphs

Jeff Erickson, Yipu Wang

Let $G$ be a directed graph with $n$ vertices and $m$ edges, embedded on a surface $S$, possibly with boundary, with first Betti number $\beta$. We consider the complexity of finding c…