Dans un article de 1999, T. Dey et S. Guha proposent un algorithme pour tester si deux lacets tracés sur une surface combinatoire sont (librement) homotopes en temps linéaire en la taille de la surface et des deux lacets. Je commencerai par montrer en quoi la méthode proposée ne fonctionne pas; puis je présenterai une solution pour la question plus simple de contractibilité d’un lacet, en m’inspirant d’un article d’É. Colin de Verdière et J. Erickson sur les raccourcissements de lacets.
This document was translated from LATEX by HEVEA.