More than a century ago, Poincaré asked for a procedure to determine if a closed curve γ on a compact surface S could be contracted to a point, and suggested a computationally expensive method. Dehn proposed a simpler combinatorial algorithm, which, optimistically, depends heavily on the genus g of the surface S. A central achievement of the Despré and Lazarus paper is an efficient algorithm for answering Poincaré’s question.

This 49-page paper contains several results, but this review concentrates on just detecting whether γ has geometric intersection number zero, equivalent to contractibility. It is assumed the surface S is given as a polygonal decomposition of total complexity n, and that γ is given as a walk on the 1-skeleton of ℓ steps. Their result is an algorithm with time complexity O(n+ℓlogℓ), independent of g.

Their work builds on that of a collection of papers over the last 50 years, which show that a series of reductions turns the problem into a purely combinatorial question. The surface is given a hyperbolic metric, which leads a unique geodesic in its “homotopic class,” its equivalence class under deformations. The surface polygonization can be reduced to a system of quadrilaterals in linear time, and a canonical form for γ can be constructed in linear time, which can be further reduced to a “homotopic geodesic,” again in linear time.

Finally, this reduced γ is untangled by the authors’ “unzipping” algorithm, which results in a simple (zero-intersection) representation exactly when γ is contractible. The proof of this is a dozen pages of delicate analysis, switching curve crossings on staircases of quadrilaterals. Dehn’s algorithm is now superseded after 100 years.