Several tools from topology are useful for mesh processing. These tools often operate on the 1-skeleton of a surface, i.e., the graph of edges embedded in the surface. A common task is to find a collection of edges called a cut graph - cutting along these paths turns the surface into a shape which can be flattened into the plane. This kind of flattening is necessary for texture mapping, remeshing, etc. The following video shows a cut graph (in yellow) on a two-handled torus, which is flattened into a disk.

A torus cut along a cut graph (yellow) becomes a disk.

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.

Computing a Greedy Homotopy Basis

A homotopy basis at x can be thought of as a homology basis where all loops meet at a common vertex x, called the basepoint. Erickson and Whittlesey prove that a shortest homotopy basis at a point on a mesh with n vertices can be computed in O(n log n) time (and subsequently, the shortest basis at any point on the mesh can be computed in O(n² log n) time).

The algorithm for finding a greedy homotopy basis is actually very simple:

1. find a tree T of shortest paths from the chosen basepoint.
2. find a maximum spanning tree T^* on the edges of the dual graph which do not cross edges in T.
3. find all edges e which are neither in T nor are crossed by edges in T^*.
4. find the shortest loops containing each e (using T) - these loops form the greedy homotopy basis.

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.

torus	double torus
quadruple torus

Globally shortest homotopy basis for several surfaces. Brightness at each vertex indicates the relative length of the greedy homotopy basis at that vertex.

For some embeddings, the function mapping vertices to basis length has many local minima.

Computing a Short Homology Basis

Rather than compute a homology basis using the method of Erickson and Whittlesey, I came up with a scheme which is simple to implement once you are able to compute the greedy homotopy basis:

1. find the genus of the surface from the Euler characteristic (χ = 2-2g for orientable surfaces).
2. compute the set L of loops from the greedy homotopy bases at every vertex.
3. sort L with respect to the total length of each loop.
4. from shortest to longest, add unique loops in L to the homology basis as long as the resulting basis leaves the surface connected, and stop once the homology basis contains 2g loops.

2. compute and add the loops in the homology basis at each vertex with a probability ξ ≤ 1.

Varying levels of approximation from left to right: ξ = 1.0, ξ = 0.1, ξ = 0.05, and ξ = 0.003. Corresponding times are 46.9 s, 6.6 s, 4 s, and 1.8 s. Note that different bases may place loops around different holes.

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

Cut Graphs

Algorithms for computing even shorter cut graphs than the ones produced by the greedy homotopy basis are slightly more complicated. As shown by Erickson and Har-Peled, computing the actual shortest cut graph is NP-hard, but they give a good approximating algorithm which runs in O(g²n logn) time. The basic idea is to cut the surface into a collection of punctured spheres by removing essential cycles, cut along a tree which connects the punctures, and glue the punctured spheres (now disks) back together. As part of my "experiment in effective proof writing," I've described the process of finding a near-optimal essential cycle in picture book form. Hopefully this makes it obvious how to find a short essential cycle through a given path:

The Story of Lemma 5.6

(I'm sorry if you don't find this amusing or don't like the fact that I've given gender to anthropomorphized paths and essential cycles.)