### Abstract

Almost exactly 100 years ago, Max Dehn 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 at most ℓ in a combinatorial surface of complexity n, our algorithm determines whether the walks are homotopic in O(n + ℓ) 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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 |

Publisher | Association for Computing Machinery |

Pages | 1646-1655 |

Number of pages | 10 |

ISBN (Print) | 9781611972511 |

DOIs | |

State | Published - 2013 |

Event | 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 - New Orleans, LA, United States Duration: Jan 6 2013 → Jan 8 2013 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 |
---|---|

Country | United States |

City | New Orleans, LA |

Period | 1/6/13 → 1/8/13 |

### ASJC Scopus subject areas

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'Transforming curves on surfaces redux'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013*(pp. 1646-1655). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery. https://doi.org/10.1137/1.9781611973105.118