Loops in Reeb graphs of 2-manifolds Journal Article


Author(s): Cole-McLaughlin, Kree; Edelsbrunner, Herbert; Harer, John; Natarajan, Vijay; Pascucci, Valerio
Article Title: Loops in Reeb graphs of 2-manifolds
Affiliation
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 the number 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.
Journal Title: Discrete & Computational Geometry
Volume: 32
Issue 2
ISSN: 0179-5376
Publisher: Springer  
Date Published: 2004-07-01
Start Page: 231
End Page: 244
Sponsor: Partially supported by NSF under Grants EIA-99-72879 and CCR-00-86013.
DOI: 10.1007/s00454-004-1122-6
Open access: no
IST Austria Authors
Related IST Austria Work