Reeb graph

Quality 0.50 · 1 view · Updated 2 months ago

Mathematical abstraction of level sets

title: "Reeb graph" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["graph-families", "application-specific-graphs"] description: "Mathematical abstraction of level sets" topic_path: "general/graph-families" source: "https://en.wikipedia.org/wiki/Reeb_graph" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Mathematical abstraction of level sets ::

::figure[src="https://upload.wikimedia.org/wikipedia/commons/4/47/3D-Leveltorus-Reebgraph.png" caption="Reeb graph of the height function on the torus."] ::

A Reeb graph (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. A similar concept was introduced by G.M. Adelson-Velskii and A.S. Kronrod and applied to analysis of Hilbert's thirteenth problem. Proposed by G. Reeb as a tool in Morse theory, Reeb graphs are the natural tool to study multivalued functional relationships between 2D scalar fields \psi, \lambda, and \phi arising from the conditions \nabla \psi = \lambda \nabla \phi and \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.

Reeb graphs have also found a wide variety of applications in computational geometry and computer graphics, including computer aided geometric design, topology-based shape matching,{{cite journal | last1 = Pascucci | first1 = Valerio | last2 = Scorzelli | first2 = Giorgio | last3 = Bremer | first3 = Peer-Timo | last4 = Mascarenhas | first4 = Ajith | title = Robust On-line Computation of Reeb Graphs: Simplicity and Speed | journal = ACM Transactions on Graphics | volume = 26 | issue = 3 | pages = 58.1–58.9 | url = http://www.pascucci.org/pdf-papers/pascucci-siggraph-2007-Reeb-Graph.pdf | year = 2007| doi = 10.1145/1276377.1276449 | last1 = Tung | first1 = Tony | last2 = Schmitt | first2 = Francis | title = The Augmented Multiresolution Reeb Graph Approach for Content-Based Retrieval of 3D Shapes | journal = International Journal of Shape Modeling | volume = 11 | issue = 1 | pages = 91–120 | url = http://sites.google.com/site/tony2ng/home/amrg | year = 2005 | doi = 10.1142/S0218654305000748 | archive-date = 2016-09-16 | access-date = 2011-05-11 | archive-url = https://web.archive.org/web/20160916025903/https://sites.google.com/site/tony2ng/home/amrg | last1 = Hajij| first1 = Mustafa | last2 = Rosen| first2 = Paul | title = An Efficient Data Retrieval Parallel Reeb Graph Algorithm | journal = Algorithms | volume = 13 | page = 258 | year = 2020| issue = 10 | doi = 10.3390/a13100258 | doi-access = free | arxiv = 1810.08310 | last1 = Shailja| first1 = S | last2 = Zhang| first2 = Angela | last3 = Manjunath| first3 = B. S. | chapter = A Computational Geometry Approach for Modeling Neuronal Fiber Pathways | title = Medical Image Computing and Computer Assisted Intervention – MICCAI 2021 | series=Lecture Notes in Computer Science | volume = 12908 | year = 2021 | pages = 175–185 | doi = 10.1007/978-3-030-87237-3_17 | pmid = 34729555 | pmc = 8560085 | isbn = 978-3-030-87236-6 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.{{citation | last1 = Carr | first1 = Hamish | last2 = Snoeyink | first2 = Jack | last3 = Axen | first3 = Ulrike | contribution = Computing contour trees in all dimensions | pages = 918–926 | title = Proc. 11th ACM-SIAM Symposium on Discrete Algorithms (SODA 2000) | contribution-url = http://portal.acm.org/citation.cfm?id=338659 | year = 2000| isbn = 978-0-89871-453-1

Formal definition

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−1(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.

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. 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.

Structure of the Reeb graph defined by a smooth function

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

The first Betti number of the Reeb graph

Since for a smooth function on a closed manifold, the Reeb graph R_f is one-dimensional, we consider only its first Betti number b_1(R_f); if R_f has the structure of a finite graph, then b_1(R_f) is the cycle rank of this graph. An upper bound holds

b_1(R_f)\le corank(\pi_1(M)),

where corank(\pi_1(M)) is the co-rank of the fundamental group of the manifold. If \dim M\ge3, this bound is tight even in the class of simple Morse functions.

If \dim M=2, for smooth functions this bound is also tight, and in terms of the genus g of the surface M^2 the bound can be rewritten as b_1(R_f)\le \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, for Morse functions, there is a better bound for the cycle rank. Since for Morse functions, the Reeb graph R_f is a finite graph, we denote by N_2 the number of vertices with degree 2 in R_f. Then b_1(R_f)\le \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}

Leaf blocks of the Reeb graph

If f:M\to R is a Morse or Morse–Bott function on a closed manifold, then its Reeb graph R_f has the structure of a finite graph. This finite graph has a specific structure, namely

If f is Morse, then R_f has no loops, and all its leaf blocks are complete graphs K_2, i.e., closed intervals
If f is Morse–Bott, then R_f has no loops, and each its leaf block contains a vertex with degree at most 2

Description for Morse functions

If 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). 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) as t passes through the critical value c. For example, if c is a minimum or a maximum of f, a component is created or destroyed; consequently, an arc originates or terminates at the corresponding node, which has degree 1. If c is a saddle point of index 1 and two components of f^{-1}(t) merge at t = c as 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 is dim X-1 and a component of f^{-1}(c) splits into two.

References

Y. Shinagawa, T.L. Kunii, and Y.L. Kergosien, 1991. Surface coding based on Morse theory. IEEE Computer Graphics and Applications, 11(5), pp.66-78
Harish Doraiswamy, Vijay Natarajan, [http://www.sciencedirect.com/science/article/pii/S0925772108001193 Efficient algorithms for computing Reeb graphs], Computational Geometry 42 (2009) 606–616
(2013). "Thermodynamic Tree: The Space of Admissible Paths". SIAM Journal on Applied Dynamical Systems.
G. M. Adelson-Velskii, A. S. Kronrod, About level sets of continuous functions with partial derivatives, Dokl. Akad. Nauk SSSR, 49 (4) (1945), pp. 239–241.
G. Reeb, Sur les points singuliers d'une forme de Pfaff complètement intégrable ou d'une fonction numérique, C. R. Acad. Sci. Paris 222 (1946) 847–849
(June 2019). "Neutral surface topology". Ocean Modelling.
Y. Shinagawa and T.L. Kunii, 1991. Constructing a Reeb graph automatically from cross sections. IEEE Computer Graphics and Applications, 11(6), pp.44-51.
M. Hilaga, Y. Shinagawa, T. Kohmura and T.L. Kunii, 2001, August. Topology matching for fully automatic similarity estimation of 3D shapes. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques (pp. 203-212). ACM.
"the Topology ToolKit".
I. Gelbukh, 2024. On the topology of the Reeb graph. Publicationes Mathematicae Debrecen, 104(3-4), pp.343-365
O. Saeki, 2022. Reeb spaces of smooth functions on manifolds. Int. Math. Res. Not., 11, pp.8740-8768
I. Gelbukh, 2018. Loops in Reeb Graphs of n-Manifolds. Discrete & Computational Geometry, 59(4), pp.843-863
L.P. Michalak, 2021. Combinatorial Modifications of Reeb Graphs and the Realization Problem. Discrete & Computational Geometry , 65, pp.1038-1060
L.P. Michalak, 2018. Realization of a graph as the Reeb graph of a Morse function on a manifold. Topological Methods in Nonlinear Analysis, 52(2), pp.749-762
I. Gelbukh, 2022. Criterion for a graph to admit a good orientation in terms of leaf blocks. Monatshefte für Mathematik, 198, pp.61-77
I. Gelbukh, 2022. Realization of a Graph as the Reeb Graph of a Morse–Bott or a Round Function. Studia Scientiarum Mathematicarum Hungarica , 59(1), pp.1-16

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::