Transforming curves on surfaces

We describe an optimal algorithm to decide if one closed curve on a triangu lated 2-manifold can be continuously transformed to another, i.e., if they are homotopic. Suppose C-1 and C-2 are two closed curves on a surface M of genus g. Further, suppose T is a triangulation of M of size n such that C-1 and C-2 are represented as edge-vertex sequences of lengths k(1) and k(2) in T,respectively. Then, our algorithm decides if C-1 and C-2 are homotopic in O(n + k(1) + k(2)) time and space, provided g not equal 2 if M is orien table, and g not equal 3, 4 if M is nonorientable. This implies as well an optimal algorithm to decide if a closed curve on a surface can be continuou sly contracted to a point. Except for three low genus cases, our algorithm completes an investigation into the computational complexity of two classic al problems for surfaces posed by the mathematician Max Dehn at the beginni ng of this century. The novelty of our approach is in the application of me thods from modern combinatorial group theory, (C) 1999 Academic Press.