Title:	Computing Dehn Twists and Geometric Intersection Numbers in Polynomial Time
Authors:	Marcus Schaefer, Eric Sedgwick, Daniel Stefankovič
Abstract:	Simple curves on surfaces are often represented as sequences of intersections with a triangulation. However, there are much more succinct ways of representing simple curves used by topologists, including normal coordinates and Dehn-Thurston coordinates. In these representations, the length of a curve might be exponential in the size of its representation. Nevertheless, we show that the following two basic tasks of computational topology, namely performing a Dehn-twist of a curve along another curve, and computing the geometric intersection number of two curves, can be solved in polynomial time even in the succinct Dehn-Thurston, or normal coordinate representations. These are the first algorithms for these two problems that solve these problems for arbitrary simple curves, and, moreover, solve them in polynomial time in the succinct representations.
Full Paper:	[ps]