  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. We present a geometric
approach based on previous works by Colin de Verdi\`ere and Erickson.
