Author(s):

ColeMcLaughlin, Kree; Edelsbrunner, Herbert; Harer, John; Natarajan, Vijay; Pascucci, Valerio

Article Title: 
Loops in Reeb graphs of 2manifolds

Affiliation 

Abstract: 
Given a Morse function f over a 2manifold 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 2manifold 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 2manifold and the Morse function.

Journal Title:

Discrete & Computational Geometry

Volume: 
32

Issue 
2

ISSN:

01795376

Publisher:

Springer

Date Published:

20040701

Start Page: 
231

End Page:

244

Sponsor: 
Partially supported by NSF under Grants EIA9972879 and CCR0086013.

DOI: 
10.1007/s0045400411226

Open access: 
no 