A simple closed curve on a surface How to describe a simple closed curve on an oriented surface of genus g? I know the answer only for the torus. It would be nice to find an article or a book where proof can be found.
 A: Check out the book Thurston's Work on Surfaces for a treatment of Dehn-Thurston coordinates which is simultaneously intuitive and in-depth.
A: First, a remark on the other two answers: The Dehn-Thurston coordinates describe multicurves (that is, disjoint unions of essential simple curves). Figuring out when a multicurve is connected (so, an actual curve) is a very difficult computational problem, though it is know through the work of yours truly (Simple curves on surfaces) and Mirzakhani (I suggest taking a look at my paper "A simpler proof of Mirzakhani's simple curve asymptotics") that there is a positive probability (which Mirzkhani expresses in terms of volumes of moduli spaces) that a multicurve (given by D-T coordinates) is a curve.
Given an element in the fundamental group, there are algorithms (Birman-Series, M. Cohen-Lustig, M. Lustig for closed surfaces) to determine whether this element represents a simple closed curve -- unfortunately, this is a decision procedure, and not a method to generate all simple closed curves.
A: There are multiple ways, depending on what your goal is. 
From an algorithmic point of view, if you are given a triangulation of the surface, normal curves are a very efficient way to describe a simple closed curve. You can check the recent paper "Tracing compressed curves in triangulated surfaces" by Jeff Erickson and Amir Nayyeri for the background.
If you want to describe curves up to isotopy, you can use Dehn-Thurston coordinates. Quick googling gave me the following link: "Dehn-Thurston Coordinates for Curves on Surfaces" by Feng Luo and Richard Strong but there are probably better references.
Finally, train tracks have proved to be a very useful method of describing curves, especially in the setting of mapping class groups. There is an orange book by Penner and Harer on them, Combinatorics of Train Tracks if I recall correctly. There is also a great survey by Lee Mosher in the Notices of the AMS.
A: Here's a pretty fast algorithm that works on punctured disks taking as input the coordinates of the multicurve.
https://link.springer.com/article/10.1007/s00229-016-0885-4
A: This paper of Boggi gives an attractive algebraic characterisation of the conjugacy classes of the fundamental group $\pi_1\Sigma$ that are represented by simple closed curves. The idea is nice and easy to explain.
If $\gamma$ is a curve on $\Sigma$, then there is a finite-sheeted covering $p:\Sigma'\to \Sigma$ in which, for every pair of components $\gamma'_1$ and $\gamma'_2$ of the preimage $p^{-1}\gamma$, any intersections of $\gamma'_1$ and $\gamma'_2$ are coherently oriented.  In particular, the algebraic intersection form on $H_1(\Sigma')$ detects whether or not $\gamma'_1$ and $\gamma'_2$ are disjoint.
This discussion gives a nice condition which can be stated purely in terms of the algebra of the fundamental group.  For a covering space $\Sigma'$ of $\Sigma$, the preimage of $\gamma$ spans a subspace $I_\gamma(\Sigma')$ of $H_1(\Sigma')$. The curve $\gamma$ is simple if and only if the restriction of the intersection form on $H_1(\Sigma')$ to $I_\gamma(\Sigma')$ is totally isotropic, for all finite-sheeted covers $\Sigma'$.
