Efficient algorithms for computing Reeb graphs

DOI10.1016/j.comgeo.2008.12.003zbMath1182.05117OpenAlexW2011751494MaRDI QIDQ924077

Harish Doraiswamy, Vijay Natarajan

Publication date: 27 July 2009

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2008.12.003

zbMATH Keywords

manifoldalgorithmslevel setReeb graphcomputational topologydynamic graphpiecewise-linear function

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A deterministic \(O(m \log {m})\) time algorithm for the Reeb graph, Avoiding the global sort: a faster contour tree algorithm, Reeb graphs: approximation and persistence, Reeb Graphs Through Local Binary Patterns, Hierarchies and Ranks for Persistence Pairs, Combining persistent homology and invariance groups for shape comparison

Uses Software

• Tulip

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Loops in Reeb graphs of 2-manifolds
• A data structure for dynamic trees
• Computing contour trees in all dimensions
• Parallel computation of the topology of level sets
• Near-optimal fully-dynamic graph connectivity
• Biased Search Trees
• Maintenance of a minimum spanning forest in a dynamic plane graph
• Topological quadrangulations of closed triangulated surfaces using the Reeb graph
• Morse-smale complexes for piecewise linear 3-manifolds
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Critical Points and Curvature for Embedded Polyhedral Surfaces