A Deterministic Time Algorithm for the Reeb Graph
We present a deterministic algorithm to compute the Reeb graph of a PL real-valued function on a simplicial complex in time, where is the size of the 2-skeleton. The problem can be solved using dynamic graph connectivity. We obtain the running time by using offline graph connectivity which assumes that the deletion time of every arc inserted is known at the time of insertion. The algorithm is implemented and experimental results are given. In addition, we reduce the offline graph connectivity problem to computing the Reeb graph.
algorithms reeb graph graph connectivity pl topology