Reeb Graphs - Mathematical Tools for Shape Analysis and Description - page 71

duce the extraction to the computation of a set of contour trees reducing the time complexity to
Om log mChm/ , where h is the number of independent loops in the Reeb graph.
Doraiswamy and Natarajan utilized an efficient tree-cotree [ 63 ] decomposition-based rep-
resentation of level sets to construct the Reeb graph in O.mg log m/ time, where m is the number
of triangles in the tetrahedral mesh representation of a 3 -manifold, and g is the maximum genus
over all level sets of the function. Using an efficient representation of the tree-cotree partition
results in an improved O.m log mCm log g. log log g/ 3 / time algorithm that for d -manifolds re-
duces to O.m log m. log log m/ 3 / operations.
Harvey et al. [ 98 ] presented the first sub-quadratic algorithm to compute the Reeb graph
for an arbitrary simplicial complex. at algorithm proposes a randomized access to the data with
an expected running time O.m log n/ , where m is the size of the 2 -skeleton of the complex (i.e.,
total number of vertices, edges and triangles), and n is the number of vertices. Finally, Parsa [ 157 ]
gave the first deterministic algorithm able to compute the Reeb graph in O.m log m/ operations
( m represents the size of the 2-skeleton), which is optimal if the number of edges of the complex
is in the same order as the number of vertices.

9.2 REEB GRAPHS ON 2 - AND 3 -MANIFOLDS
As a consequence of its ability to extract high-level features from shapes, the Reeb graph is an ef-
fective tool for shape analysis and description, especially in case of 2 - and 3 -manifolds. Figure 9.1
shows two examples of Reeb graphs of a closed surface. In Figure 9.1 (a) some level sets of the
height function are drawn with the corresponding Reeb graph; in Figure 9.1 (b) the Reeb graph
of the same object is shown using the Euclidean distance from a point.

(a) (b)

Figure 9.1: Reeb graphs with respect to the height function (a) and the distance from the point
p (b) [ 24 ].

For orientable, closed 2 -manifolds, the number of cycles in the Reeb graph corresponds
to the genus of the manifold, and this result has been generalized in [ 48 ], where the authors
demonstrate that the number 1 .M/ of non-homologous loops of the surface is an upper bound
of the number of loops 1 .K/ of the Reeb graph. e equality holds in case of orientable surfaces
without boundary [ 48 ], while, in general, the following relation is satisfied:

g 1 .K/2gCb M 1;