On the homotopy test on surfaces

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 are homotopic in S, either freely or with fixed basepoint. We restrict S to be orientable for the free homotopy test, but allow non-orientable surfaces when the basepoint is fixed. After O(|G|) time preprocessing independent of c and d, our algorithms answer the homotopy test in O(|c | + |d|) time, where |G|, |c | and |d | are the respective numbers of edges of G, c and d. As a byproduct we obtain linear time algorithms for the word problem and the conjugacy problem in surface groups. These results were previously announced by Dey and Guha (1999). Their approach was based on small cancellation theory from combinatorial group theory. However, several flaws in their algorithms make their approach fails, leaving the complexity of the homotopy test problem still open. We present a geometric approach, based on previous works by Colin de Verdière and Erickson, that provides optimal homotopy tests.