Proceedings of the 24rd Annual ACM-SIAM Symposium on Discrete Algorithms, 1646–1655, 2013.

Abstract:

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 lengthlandl′in a combinatorial surface of complexityn, our algorithm determines whether the two walks are freely homotopic in O(n+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.+l′

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 15 Feb 2013