Session A4 - Computational Geometry and Topology
July 12, 15:30 ~ 15:55 - Room B7
Deciding contractibility of a non-simple curve on the boundary of a 3-manifold
Éric Colin de Verdière
CNRS, LIGM, Université Paris-Est Marne-la-Vallée, France - firstname.lastname@example.org
We present an algorithm for the following problem: Given a triangulated 3-manifold $M$ and a (possibly non-simple) closed curve on the boundary of $M$, decide whether this curve is contractible in $M$. Our algorithm is combinatorial and runs in exponential time. This is the first algorithm that is specifically designed for this problem; its running time considerably improves upon the existing bounds implicit in the literature for the more general problem of contractibility of closed curves in a $3$-manifold. The proof of the correctness of the algorithm relies on methods of $3$-manifold topology and in particular on those used in the proof of the Loop Theorem.
Joint work with Salman Parsa (Mathematical Sciences Department, Sharif University of Technology, Tehran, Iran).