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 base point. 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. 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 fail, 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.