TitleLoops in Reeb graphs of 2-manifolds (Article)
inDiscrete and Computational Geometry
Author(s) Kree Cole-McLaughlin, Herbert Edelsbrunner, John Harer, Vijay Natarajan, Valerio Pascucci
Keyword(s)Computational topology, 2-manifolds, Morse functions, level sets, Reeb graphs, loops, algorithms.
Year 2004
Abstract Given a Morse function $f$ over a 2-manifold with or without boundary, the Reeb graph is obtained by contracting the connected components of the level sets to points. We prove tight upper and lower bounds on thenumber of loops in the Reeb graph that depend on the genus, the number of boundary components,and whether or not the 2-manifold is orientable. We also give an algorithm that constructs the Reeb graph in time O($n \log n$), where $n$ is the number of edges in the triangulation used to represent the 2-manifold and the Morse function.