Stability of Reeb Graphs of Closed Curves

Reeb graphs are very popular shape descriptors in computational frameworks as they capture both geometrical properties of the shape, and its topological features. Some different methodologies have been proposed in the literature to estimate the similarity of shapes through the comparison of the associated Reeb graphs. In this context, one of the most important open questions is whether Reeb graphs are robust against function perturbations. In fact, it is clear that any data acquisition is subject to perturbations, noise and approximation errors and, if Reeb graphs were not stable, then distinct computational investigations of the same object could produce completely different results. In this paper we present an initial contribution to establishing stability properties for Reeb graphs. More precisely, focusing our attention on 1-dimensional manifolds, we define an editing distance between Reeb graphs, in terms of the cost necessary to transform one graph into another. Our main result is that changes in Morse functions imply smaller changes in the editing distance between Reeb graphs.