Transforming Curves on Surfaces Redux

Almost exactly 100 years ago, Max Dehn [Math. Ann. 1912] described the first combinatorial algorithm to determine whether two given cycles on a compact surface are homotopic, meaning one cycle can be continuously deformed into the other without leaving the surface. We describe a simple variant of Dehn’s algorithm that runs in linear time, with no hidden dependence on the genus of the surface. Specifically, given two closed vertex-edge walks of length l and l′ in a combinatorial surface of complexity n, our algorithm determines whether the two walks are freely homotopic in O(n + l + l′) time. Our algorithm simplifies and corrects a similar algorithm of Dey and Guha [JCSS 1999] and simplifies the more recent algorithm of Lazarus and Rivaud [FOCS 2012], who identified a subtle flaw in Dey and Guha’s results. Our algorithm combines components of these earlier algorithms, classical results in small cancellation theory by Gersten and Short [Inventiones 1990], and simple run-length encoding.

Transforming curves on surfaces redux