A deterministic o(m log m) time algorithm for the reeb graph
Salman Parsa · 2012
We present a deterministic algorithm to compute the Reeb graph of a PL real-valued function on a simplicial complex in O(m log m) time, where m is the size of the 2-skeleton. The problem reduces to dynamic graph connectivity. We obtain the running time by using offline graph connectivity which assumes that the sequence of operations is known in advance. The algorithm is implemented and experimental results are given. In addition, we reduce the offline graph connectivity problem to computing the Reeb graph.