Determining contractibility of curves
Haijo Schipper · 1992
In this paper we will present an algorithm to' determine whether a curve on a triangulated 2-manifold is contractible ( or O-homotopic) or not, that is whether it can be contracted to a point or not.The algorithm will work in O ( g2k + gn) time, using O ( g2k + gn) storage, where g is the genus of the surface, n the number of triangles of the surfaces, and k the number of edges of the curve.We will also give an algorithm which constructs the contraction if the curve is O-homotopic.This algorithm runs in O ( g2kn) time and storage.The algorithm can obviously be applied to determine whether two curves are homotopic, and if so, to construct the homotopy.