Author(s):

Bauer, Ulrich; Ge, Xiaoyin; Wang, Yusu

Title: 
Measuring distance between Reeb graphs

Affiliation 
IST Austria 
Abstract: 
We propose a metric for Reeb graphs, called the functional distortion distance. Under this distance, the Reeb graph is stable against small changes of input functions. At the same time, it remains discriminative at differentiating input functions. In particular, the main result is that the functional distortion distance between two Reeb graphs is bounded from below by the bottleneck distance between both the ordinary and extended persistence diagrams for appropriate dimensions. As an application of our results, we analyze a natural simplification scheme for Reeb graphs, and show that persistent features in Reeb graph remains persistent under simplification. Understanding the stability of important features of the Reeb graph under simplification is an interesting problem on its own right, and critical to the practical usage of Reeb graphs. Copyright is held by the owner/author(s).

Conference Title:

SoCG: Symposium on Computational Geometry

Conference Dates:

June 811, 2014

Conference Location:

Kyoto, Japan

ISBN:

9781450325943

Publisher:

ACM

Date Published:

20140601

Start Page: 
464

End Page:

473

Sponsor: 
National Science Foundation under grants CCF1319406, CCF1116258, and by the Toposys project FP7ICT318493STREP.

URL: 

DOI: 
10.1145/2582112.2582169

Notes: 
We thank Facundo MĂ©moli for helpful discussions about variants of the Gromovâ€“Hausdorff distance, which lead to improvements in our definition of the functional distortion distance.

Open access: 
yes (repository) 