Reeb graph

<h2 id="formal-definition">Formal definition</h2>
Given a <a href="/facts/Topological_space/v2ut7CbK">topological space</a> X and a <a href="/facts/Continuous_function/sKbl02pB">continuous function</a> f: X → R, define an <a href="/facts/Equivalence_relation/1MQ5rtkW">equivalence relation</a> ~ on X where p~q whenever p and q belong to the same <a href="/facts/Connected_component_(topology)/5CUTxfoA">connected component</a> of a single <a href="/facts/Level_set/JUmNbdNh">level set</a> f−1(c) for some real c. The Reeb graph is the <a href="/facts/Quotient_space_(topology)/muE0qQVC">quotient space</a> X /~ endowed with the <a href="/facts/Quotient_topology/muE0qQVC">quotient topology</a>.
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-<a href="/facts/Hausdorff_space/gbKIrusl">Hausdorff space</a>.<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a>
In fact, the <a href="/facts/Compactness/d0cgXJH7">compactness</a> of the manifold is crucial: The Reeb graph of a smooth function on a closed manifold is a one-dimensional <a href="/facts/Peano_continuum/MBAh8aro">Peano continuum</a> that is <a href="/facts/Homotopy_equivalence/1nWrPxdj">homotopy equivalent</a> to a finite graph.<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a>
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 <a href="/facts/Morse_function/bJRqH8BQ">Morse functions</a>, <a href="/facts/Morse%E2%80%93Bott_function/bJRqH8BQ">Morse–Bott functions</a> or functions with isolated critical points – has the structure of a finite graph.<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a>

<h2 id="structure-of-the-reeb-graph-defined-by-a-smooth-function">Structure of the Reeb graph defined by a smooth function</h2>
Let 
 
 
 
 f
 :
 M
 →
 
 
 R
 
 
 
 
 {\displaystyle f:M\to {\mathbb {R} }}
 
 be a <a href="/facts/Smooth_function/mffL4ch2">smooth function</a> on a <a href="/facts/Closed_manifold/jMG6G6Bl">closed manifold</a> 
 
 
 
 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}
 
.

<h3>The first Betti number of the Reeb graph</h3>
Since for a smooth function on a closed manifold, the Reeb graph 
 
 
 
 
 R
 
 f
 
 
 
 
 {\displaystyle R_{f}}
 
 is one-dimensional,<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a> we consider only its first <a href="/facts/Betti_number/r42Y8k6f">Betti number</a> 
 
 
 
 
 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 <a href="/facts/Circuit_rank/RqbfVDR6">cycle rank</a> of this graph. An upper bound holds<a class="footnote-ref" id="fnref:22" href="#fn:22">22</a><a class="footnote-ref" id="fnref:23" href="#fn:23">23</a> 

 
 
 
 
 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 <a href="/facts/Rank_of_a_group/tqC9KFwI">co-rank</a> of the <a href="/facts/Fundamental_group/VyYtLqSP">fundamental group</a> of the manifold. If 
 
 
 
 dim
 ⁡
 M
 ≥
 3
 
 
 {\displaystyle \dim M\geq 3}
 
, this bound is tight even in the class of simple <a href="/facts/Morse_function/bJRqH8BQ">Morse functions</a>.<a class="footnote-ref" id="fnref:24" href="#fn:24">24</a> 
If 
 
 
 
 dim
 ⁡
 M
 =
 2
 
 
 {\displaystyle \dim M=2}
 
, for <a href="/facts/Smooth_function/mffL4ch2">smooth functions</a> this bound is also tight, and in terms of the <a href="/facts/Genus/m8EFjSms">genus</a> 
 
 
 
 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 <a href="/facts/Morse_function/bJRqH8BQ">Morse functions</a>, there is a better bound for the cycle rank. Since for <a href="/facts/Morse_function/bJRqH8BQ">Morse functions</a>, the Reeb graph 
 
 
 
 
 R
 
 f
 
 
 
 
 {\displaystyle R_{f}}
 
 is a finite graph,<a class="footnote-ref" id="fnref:25" href="#fn:25">25</a> we denote by 
 
 
 
 
 N
 
 2
 
 
 
 
 {\displaystyle N_{2}}
 
 the number of <a href="/facts/Vertex_(graph_theory)/WhlWmL3o">vertices</a> with <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a> 2 in 
 
 
 
 
 R
 
 f
 
 
 
 
 {\displaystyle R_{f}}
 
. Then<a class="footnote-ref" id="fnref:26" href="#fn:26">26</a>

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

<h3>Leaf blocks of the Reeb graph</h3>
If 
 
 
 
 f
 :
 M
 →
 R
 
 
 {\displaystyle f:M\to R}
 
 is a <a href="/facts/Morse_function/bJRqH8BQ">Morse</a> or <a href="/facts/Morse_theory/bJRqH8BQ">Morse–Bott function</a> on a <a href="/facts/Closed_manifold/jMG6G6Bl">closed manifold</a>, then its Reeb graph 
 
 
 
 
 R
 
 f
 
 
 
 
 {\displaystyle R_{f}}
 
 has the structure of a finite graph.<a class="footnote-ref" id="fnref:27" href="#fn:27">27</a> This finite graph has a specific structure, namely

<ul><li>If 
 
 
 
 f
 
 
 {\displaystyle f}
 
 is <a href="/facts/Morse_function/bJRqH8BQ">Morse</a>, then 
 
 
 
 
 R
 
 f
 
 
 
 
 {\displaystyle R_{f}}
 
 has no <a href="/facts/Loop_(graph_theory)/jCuevIad">loops</a>, and all its <a href="/facts/Biconnected_component/Y4221AkA">leaf blocks</a> are <a href="/facts/Complete_graph/AYD6hUqI">complete graphs</a> 
 
 
 
 
 K
 
 2
 
 
 
 
 {\displaystyle K_{2}}
 
, i.e., closed intervals<a class="footnote-ref" id="fnref:28" href="#fn:28">28</a></li>
<li>If 
 
 
 
 f
 
 
 {\displaystyle f}
 
 is <a href="/facts/Morse_theory/bJRqH8BQ">Morse–Bott</a>, then 
 
 
 
 
 R
 
 f
 
 
 
 
 {\displaystyle R_{f}}
 
 has no <a href="/facts/Loop_(graph_theory)/jCuevIad">loops</a>, and each its <a href="/facts/Biconnected_component/Y4221AkA">leaf block</a> contains a <a href="/facts/Vertex_(graph_theory)/WhlWmL3o">vertex</a> with <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a> at most 2<a class="footnote-ref" id="fnref:29" href="#fn:29">29</a></li></ul>
<h2 id="description-for-morse-functions">Description for Morse functions</h2>
If 
 
 
 
 f
 
 
 {\displaystyle f}
 
 is a <a href="/facts/Morse_function/bJRqH8BQ">Morse function</a> with distinct <a href="/facts/Critical_value_(critical_point)/MrEk9PnY">critical values</a>, 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 <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a> 1. If 
 
 
 
 c
 
 
 {\displaystyle c}
 
 is a <a href="/facts/Saddle_point/v5MT6YbM">saddle point</a> 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.

<h2 id="references">References</h2>

<ol>
<li id="fn:1">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 <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Harish Doraiswamy, Vijay Natarajan, Efficient algorithms for computing Reeb graphs, Computational Geometry 42 (2009) 606–616 <a href="http://www.sciencedirect.com/science/article/pii/S0925772108001193" target="_blank">http://www.sciencedirect.com/science/article/pii/S0925772108001193</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Gorban, Alexander N. (2013). "Thermodynamic Tree: The Space of Admissible Paths". SIAM Journal on Applied Dynamical Systems. 12 (1): 246–278. arXiv:1201.6315. doi:10.1137/120866919. S2CID 5706376. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">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. <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">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 <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Stanley, Geoffrey J. (June 2019). "Neutral surface topology". Ocean Modelling. 138: 88–106. arXiv:1903.10091. Bibcode:2019OcMod.138...88S. doi:10.1016/j.ocemod.2019.01.008. S2CID 85502820. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">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 <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">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. <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Pascucci, Valerio; Scorzelli, Giorgio; Bremer, Peer-Timo; Mascarenhas, Ajith (2007). "Robust On-line Computation of Reeb Graphs: Simplicity and Speed" (PDF). ACM Transactions on Graphics. 26 (3): 58.1 – 58.9. doi:10.1145/1276377.1276449. <a href="http://www.pascucci.org/pdf-papers/pascucci-siggraph-2007-Reeb-Graph.pdf" target="_blank">http://www.pascucci.org/pdf-papers/pascucci-siggraph-2007-Reeb-Graph.pdf</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">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. <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Tung, Tony; Schmitt, Francis (2005). "The Augmented Multiresolution Reeb Graph Approach for Content-Based Retrieval of 3D Shapes". International Journal of Shape Modeling. 11 (1): 91–120. doi:10.1142/S0218654305000748. <a href="https://sites.google.com/site/tony2ng/home/amrg" target="_blank">https://sites.google.com/site/tony2ng/home/amrg</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">"the Topology ToolKit". <a href="https://topology-tool-kit.github.io/" target="_blank">https://topology-tool-kit.github.io/</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Hajij, Mustafa; Rosen, Paul (2020). "An Efficient Data Retrieval Parallel Reeb Graph Algorithm". Algorithms. 13 (10): 258. arXiv:1810.08310. doi:10.3390/a13100258. <a href="https://doi.org/10.3390%2Fa13100258" target="_blank">https://doi.org/10.3390%2Fa13100258</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Shailja, S; Zhang, Angela; Manjunath, B. S. (2021). "A Computational Geometry Approach for Modeling Neuronal Fiber Pathways". Medical Image Computing and Computer Assisted Intervention – MICCAI 2021. Lecture Notes in Computer Science. Vol. 12908. pp. 175–185. doi:10.1007/978-3-030-87237-3_17. ISBN 978-3-030-87236-6. PMC 8560085. PMID 34729555. <a href="978-3-030-87236-6" target="_blank">978-3-030-87236-6</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Gorban, Alexander N. (2013). "Thermodynamic Tree: The Space of Admissible Paths". SIAM Journal on Applied Dynamical Systems. 12 (1): 246–278. arXiv:1201.6315. doi:10.1137/120866919. S2CID 5706376. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Carr, Hamish; Snoeyink, Jack; Axen, Ulrike (2000), "Computing contour trees in all dimensions", Proc. 11th ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), pp. 918–926, ISBN 9780898714531. <a href="9780898714531" target="_blank">9780898714531</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Klemelä, Jussi (2018). "Level set tree methods". Wiley Interdisciplinary Reviews: Computational Statistics. 10 (5): e1436. doi:10.1002/wics.1436. S2CID 58864566. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">I. Gelbukh, 2024. On the topology of the Reeb graph. Publicationes Mathematicae Debrecen, 104(3-4), pp.343-365 <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">I. Gelbukh, 2024. On the topology of the Reeb graph. Publicationes Mathematicae Debrecen, 104(3-4), pp.343-365 <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">O. Saeki, 2022. Reeb spaces of smooth functions on manifolds. Int. Math. Res. Not., 11, pp.8740-8768 <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">I. Gelbukh, 2024. On the topology of the Reeb graph. Publicationes Mathematicae Debrecen, 104(3-4), pp.343-365 <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">I. Gelbukh, 2018. Loops in Reeb Graphs of n-Manifolds. Discrete & Computational Geometry, 59(4), pp.843-863 <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">I. Gelbukh, 2024. On the topology of the Reeb graph. Publicationes Mathematicae Debrecen, 104(3-4), pp.343-365 <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
<li id="fn:24">L.P. Michalak, 2021. Combinatorial Modifications of Reeb Graphs and the Realization Problem. Discrete & Computational Geometry , 65, pp.1038-1060 <a href="#fnref:24" class="footnote-back-ref">↩</a></li>
<li id="fn:25">O. Saeki, 2022. Reeb spaces of smooth functions on manifolds. Int. Math. Res. Not., 11, pp.8740-8768 <a href="#fnref:25" class="footnote-back-ref">↩</a></li>
<li id="fn:26">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 <a href="#fnref:26" class="footnote-back-ref">↩</a></li>
<li id="fn:27">O. Saeki, 2022. Reeb spaces of smooth functions on manifolds. Int. Math. Res. Not., 11, pp.8740-8768 <a href="#fnref:27" class="footnote-back-ref">↩</a></li>
<li id="fn:28">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 <a href="#fnref:28" class="footnote-back-ref">↩</a></li>
<li id="fn:29">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 <a href="#fnref:29" class="footnote-back-ref">↩</a></li>
</ol>

Reeb graph open-in-new

Reeb graph