The Reeb graph is a tool from Morse theory that has recently found use in applied topology due to its ability to track the changes in connectivity of level sets of a function. The roadmap, a construction that arises in semi-algebraic geometry, is a one-dimensional set that encodes information about the connected components of a set. In this talk, I will present an algorithm with singly-exponential complexity that realizes the Reeb graph of a function $f: X\to R$ as a semi-algebraic quotient using the roadmap of $X$ with respect to $f$. We then generalize our result by constructing an algorithm to realize the Reeb space of a function $f: X \to Y$ with doubly exponential complexity in $\dim(Y)$.
An Efficient Algorithm for the Computation of Reeb Spaces from Roadmaps
Sarah Percival, Michigan State University
2022 AWM Research Symposium
Women in Computational Topology