Algorithms to find simple closed curves on a surface

Fix a triangulation $T = (t_i)_{i=0}^N$ of the surface $S$. An arc $\alpha$ embedded in a triangle $t_i$ is normal if the two points $\partial \alpha$ lie in distinct edges of $t_i$. A single triangle $t_i$ admits three different normal arcs (up to isotopy).

A simple closed curve $\alpha \subset S$ is normal with respect to $T$ if and only if $\alpha \cap t_i$ is a collection of normal arcs for each $i$. Exercise: every essential simple curve may be isotoped to be normal. We may replace any normal curve by a vector of length $3N$ by counting the number of each type of normal arc. These vectors have non-negative integer entries and satisfy certain "matching equations". Conversely, any such vector represents a simple closed multicurve. (Note that a single isotopy class of curve may have many different representations as a normal curve!)

The matching equations cut a cone out of the positive orthant. Thus to enumerate all curves up to a fixed length (where here I count the number of normal arcs as the length) it suffices to find a Hilbert basis for this cone and take all combinations up to a fixed size, and so on, and so on.

The result is an algorithm that enumerates all essential simple closed curves up to length $N$ in time polynomial in $N$. However the precomputation (of the Hilbert basis for the cone, etc) is no joke.

You can find a discussion starting on page 13 of Cameron Gordon's notes for a course on normal surfaces in three-manifolds. I'll end with a remark: in the case of the (once-holed) torus you can get away with exactly two triangles, the cone is very simple, the basis is very pretty, and everything can be done by hand. (In fact you can this way rediscover for yourself the classification of simple closed curves in the torus.)

Edit: I'll add one more remark. You are representing curves on the surface via "cutting sequences" which are very closely related to writing out words in terms of the fundamental group. When working with simple curves (and the simplicity is crucial here) it can be exponentially more efficient to use the "normal coordinates" I described. These are very similar to Thurston's "train track" coordinates for simple closed curves. There is a third way to represent simple curves: Fix a small collection of curves (ie the very short curves) and then act on those by the mapping class group of the surface, as generated by Dehn twists (say). These "mapping class group coordinates" can again be exponentially more efficient than using cutting sequences.