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

C H A P T E R 9

Reeb Graphs

Reeb graphs encode the evolution and the arrangement of the level sets of a real function defined
on a shape. ey were first defined by a French mathematician, Georges Reeb, in 1946 [ 166 ] as
topological constructs. In recent years, Reeb graphs have become popular in computer graphics
as tools for shape description, analysis and comparison.
Reeb graphs present a framework for studying a shape on the basis of an arbitrarily chosen
real function. ey effectively code both topological and geometrical information; the topologi-
cal analysis is driven by the evolution of the level sets of the function chosen and the geometry
properties reflect the shape of the contours. Different functions give insights on the shape from
different perspectives and the properties of the resulting graphs are parametric to these functions.

9.1 REEB GRAPH DEFINITION
Given a manifold M and a real-valued function f defined on M , the simplicial complex defined
by Reeb, conventionally called the Reeb graph, is the quotient space defined by the equivalence
relation that identifies the points belonging to the same connected component of level sets of f .
Under some hypotheses on M and f , Reeb stated the following theorem, which actually defines
the Reeb graph.

eorem 9.1 Let M be a compact n -dimensional manifold and f a simple ¹ Morse function defined
on M , and let us define the equivalence relation “ ” as .P;f.P//.Q;f.Q// iff f.P/Df.Q/
and P , Q are in the same connected component of f

1 .f.P// . e quotient space on MR induced
by “ ” is a finite and connected simplicial complex K of dimension 1 , such that the counter-image of
each vertex 0 i of K is a singular connected component of the level sets of f , and the counter-image of
the interior of each simplex 1 j is homeomorphic to the topological product of one connected component
of the level sets by R [ 74 , 166 ].

Reeb also demonstrated the following theorems, which clarify the relations between the
degree, or order, of the vertices of the simplicial complex K associated with the quotient space
and the index of the corresponding critical points.

e degree of a vertex 0 i of index 0 (or n ) is 1 and the index of a vertex 0 i of degree

eorem 9.2

1 is 0 or n .

¹A function is called simple if its critical points have different values.