Intuitively, homology is a tool for studying different dimensional holes of
a topological space. The homology of one-dimensional cycles in surfaces
have been studied for their applications in computer science, and several
algorithms have been proposed to compute with them. The first step of many
of these algorithms is computing a basis of the homology group.
In this talk, we consider the problem of finding a shortest basis for the
homology group of an orientable surface. We briefly discuss its relation
with the well-known minimum cycle basis problem from graph theory. Then,
we mention a couple of old methods to compute the shortest homology basis.
Finally, we present a recent nearly linear time algorithm for this problem.
This is a joint work with Erin Chambers and Kyle Fox.