One way to find a cut graph is to find a set of loops, no two of which are homologous, which cut the surface into a disk when removed. Intuitively, two loops on a surface are homologous if one can be deformed into the other while always keeping it entirely on the surface. For a closed orientable surface with genus g (i.e., a torus with g handles), there are 2g classes of homologically independent loops. A homology basis consists of one loop from each class. Not every homology basis is a cut graph: some homology bases either disconnect the surface or cut it into a punctured sphere. However, a greedy homotopy basis (described below) will cut the surface into a disk.
The algorithm for finding a greedy homotopy basis is actually very simple:
The images below help illustrate this process. The magenta square is the chosen basepoint. Light blue arrows in the left image are edges in T, pointing toward their predecessor (note that the basepoint is at the root of the tree). Glowing lines in the center image highlight edges of the dual graph, and yellow arrows point to their predecessors in T^{*}. The final image superimposes T and T^{*}  notice that the two trees do not cross eachother. (No edges in the greedy homotopy basis are visible in this closeup of the surface.)
Left: tree of shortest paths. Center: maximum spanning tree. Right: the two trees superimposed.
The video below shows the greedy homotopy basis for each vertex of the mesh (again, the magenta square is the current basepoint). Out of curiousity, I also plotted the total length of the homotopy basis at each point  see the shaded surfaces below. The brightness of a vertex corresponds to the relative length of its corresponding basis. Because this function is fairly smooth, it might be used to quickly search for an approximation of the globally shortest homotopy basis. However, the function has many local minima over some embeddings.
Animation of the greedy homotopy basis at each basepoint.
For some embeddings, the function mapping vertices to basis length has many local minima.


Short homology basis on double torus (ξ = 1.0). 
Short homology basis on quadruple torus (ξ = 0.05). 