||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
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.
- performing a Dehn-twist of a curve along another curve, and
- computing the geometric intersection number of two curves,