"Transforming Curves on Surfaces Redux"

Jeff Erickson, University of Illinois

Thursday, June 21, 2012 at 12:00 Noon

Room 368 (CIT 3rd Floor)

Almost exactly 100 years ago, Max Dehn described the first 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. Our algorithm simplifies and corrects a similar algorithm of Dey and Guha (1999) and simplifies a recent algorithm of Francis and Rivaud (2011), 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 (1990), and simple run-length encoding.

The talk will be self-contained; I will introduce all necessary concepts from topology and small cancellation theory. This is unpublished joint work with Kim Whittlesey.

Host: Philip Klein