Potential functions are typically visualized by individual level sets, which for three-dimensional functions are also known as iso-surfaces. Examples are the electron densities obtained from x-ray diffraction patterns observed for crystallized protein structures. The shape of a single protein structure is visible in this density as an iso-surface or a family of iso-surfaces for judiciously chosen threshold values. The Reeb graph of a potential function is obtained by contracting each component of every level set to a point.

Reeb graphs compress the information inherent in the family of level sets into one intuitive picture and are therefore useful in visualization. They are also used to speed up algorithms for constructing level sets, such as the marching cube algorithm. When used in this capacity, Reeb graphs are often referred to as contour trees, although they are trees only for functions over simply-connected domains.

In this project, we study the structure of Reeb graphs and we design efficient algorithms for constructing them. We have analyzed the number of loops in the Reeb graph of a function over a 2-manifold with or without boundary. For example, we have shown that for an orientable 2-manifold with genus g and no boundary there are always g loops, but for a similar non-orientable 2-manifold there are between zero and g/2 loops. We have also given an algorithm that constructs the Reeb graph in time O((n+g)logn), where n is the size of the triangulation used to represent the 2-manifold. By combining our understanding of the structure of Reeb graphs with the ideas of topological persistence, we obtain hierarchies of progressively simpler Reeb graphs. These are important in applications where the sheer size challenges the direct visualization of the data. Our understanding of Reeb graphs for functions over 3-manifolds is much less complete, and we plan to study their topological and computational properties next.