Reeb graph

A Reeb graph^[1] (named after Georges Reeb by René Thom) is a mathematical object reflecting the evolution of the level sets of a real-valued function on a manifold.^[2] A similar concept was introduced by G.M. Adelson-Velskii and A.S. Kronrod and applied to analysis of Hilbert's thirteenth problem.^[3][4] Proposed by G. Reeb as a tool in Morse theory,^[5] Reeb graphs are the natural tool to study multivalued functional relationships between 2D scalar fields ψ {\displaystyle \psi } , λ {\displaystyle \lambda } , and ϕ {\displaystyle \phi } arising from the conditions ∇ ψ = λ ∇ ϕ {\displaystyle \nabla \psi =\lambda \nabla \phi } and λ ≠ 0 {\displaystyle \lambda \neq 0} , because these relationships are single-valued when restricted to a region associated with an individual edge of the Reeb graph. This general principle was first used to study neutral surfaces in oceanography.^[6]

Reeb graphs have also found a wide variety of applications in computational geometry and computer graphics,^[1][7] including computer aided geometric design, topology-based shape matching,^[8][9][10] topological data analysis,^[11] topological simplification and cleaning, surface segmentation ^[12] and parametrization, efficient computation of level sets, neuroscience,^[13] and geometrical thermodynamics.^[3] In a special case of a function on a flat space (technically a simply connected domain), the Reeb graph forms a polytree and is also called a contour tree.^[14]

Level set graphs help statistical inference related to estimating probability density functions and regression functions, and they can be used in cluster analysis and function optimization, among other things. ^[15]

Given a topological space X and a continuous function f: X → R, define an equivalence relation ~ on X where p~q whenever p and q belong to the same connected component of a single level set f⁻¹(c) for some real c. The Reeb graph is the quotient space X /~ endowed with the quotient topology.

Generally, this quotient space does not have the structure of a finite graph. Even for a smooth function on a smooth manifold, the Reeb graph can be not one-dimensional and even non-Hausdorff space.^[16]

In fact, the compactness of the manifold is crucial: The Reeb graph of a smooth function on a closed manifold is a one-dimensional Peano continuum that is homotopy equivalent to a finite graph.^[16] In particular, the Reeb graph of a smooth function on a closed manifold with a finite number of critical values –which is the case of Morse functions, Morse–Bott functions or functions with isolated critical points – has the structure of a finite graph.^[17]

Let f : M → R {\displaystyle f:M\to {\mathbb {R} }} be a smooth function on a closed manifold M {\displaystyle M} . The structure of the Reeb graph R f {\displaystyle R_{f}} depends both on the manifold M {\displaystyle M} and on the class of the function f {\displaystyle f} .

Since for a smooth function on a closed manifold, the Reeb graph R f {\displaystyle R_{f}} is one-dimensional,^[16] we consider only its first Betti number b 1 ( R f ) {\displaystyle b_{1}(R_{f})} ; if R f {\displaystyle R_{f}} has the structure of a finite graph, then b 1 ( R f ) {\displaystyle b_{1}(R_{f})} is the cycle rank of this graph. An upper bound holds^[18][16]

b 1 ( R f ) ≤ c o r a n k ( π 1 ( M ) ) {\displaystyle b_{1}(R_{f})\leq corank(\pi _{1}(M))} ,

where c o r a n k ( π 1 ( M ) ) {\displaystyle corank(\pi _{1}(M))} is the co-rank of the fundamental group of the manifold. If dim ⁡ M ≥ 3 {\displaystyle \dim M\geq 3} , this bound is tight even in the class of simple Morse functions.^[19]

If dim ⁡ M = 2 {\displaystyle \dim M=2} , for smooth functions this bound is also tight, and in terms of the genus g {\displaystyle g} of the surface M 2 {\displaystyle M^{2}} the bound can be rewritten as b 1 ( R f ) ≤ { g , if  M 2  is orientable  g / 2 , if  M 2  is non-orientable  . {\displaystyle b_{1}(R_{f})\leq {\begin{cases}g,&{\text{if }}M^{2}{\text{ is orientable }}\\g/2,&{\text{if }}M^{2}{\text{ is non-orientable }}.\end{cases}}}

If dim ⁡ M = 2 {\displaystyle \dim M=2} , for Morse functions, there is a better bound for the cycle rank. Since for Morse functions, the Reeb graph R f {\displaystyle R_{f}} is a finite graph,^[17] we denote by N 2 {\displaystyle N_{2}} the number of vertices with degree 2 in R f {\displaystyle R_{f}} . Then^[20] b 1 ( R f ) ≤ { g − N 2 , if  M 2  is orientable  ( g − N 2 ) / 2 , if  M 2  is non-orientable  . {\displaystyle b_{1}(R_{f})\leq {\begin{cases}g-N_{2},&{\text{if }}M^{2}{\text{ is orientable }}\\(g-N_{2})/2,&{\text{if }}M^{2}{\text{ is non-orientable }}.\end{cases}}}

If f : M → R {\displaystyle f:M\to R} is a Morse or Morse–Bott function on a closed manifold, then its Reeb graph R f {\displaystyle R_{f}} has the structure of a finite graph.^[17] This finite graph has a specific structure, namely

• If f {\displaystyle f} is Morse, then R f {\displaystyle R_{f}} has no loops, and all its leaf blocks are complete graphs K 2 {\displaystyle K_{2}} , i.e., closed intervals^[21]
• If f {\displaystyle f} is Morse–Bott, then R f {\displaystyle R_{f}} has no loops, and each its leaf block contains a vertex with degree at most 2^[22]

If f {\displaystyle f} is a Morse function with distinct critical values, the Reeb graph can be described more explicitly. Its nodes, or vertices, correspond to the critical level sets f − 1 ( c ) {\displaystyle f^{-1}(c)} . The pattern in which the arcs, or edges, meet at the nodes/vertices reflects the change in topology of the level set f − 1 ( t ) {\displaystyle f^{-1}(t)} as t {\displaystyle t} passes through the critical value c {\displaystyle c} . For example, if c {\displaystyle c} is a minimum or a maximum of f {\displaystyle f} , a component is created or destroyed; consequently, an arc originates or terminates at the corresponding node, which has degree 1. If c {\displaystyle c} is a saddle point of index 1 and two components of f − 1 ( t ) {\displaystyle f^{-1}(t)} merge at t = c {\displaystyle t=c} as t {\displaystyle t} increases, the corresponding vertex of the Reeb graph has degree 3 and looks like the letter "Y". The same reasoning applies if the index of c {\displaystyle c} is d i m X − 1 {\displaystyle dimX-1} and a component of f − 1 ( c ) {\displaystyle f^{-1}(c)} splits into two.