On the homotopy test on surfaces

Francis Lazarus, Julien Rivaud

Let G be a graph cellularly embedded in a surface S. Given two closed walks c and d in G, we take advantage of the RAM model to describe linear time algorithms to decide if c and d…