Stable shape comparison of surfaces via Reeb graphs

Reeb graphs are combinatorial signatures that capture shape properties from the perspective of a chosen function. One of the most important questions is whether Reeb graphs are robust against function perturbations that may occur because of noise and approximation errors in the data acquisition process. In this work we tackle the problem of stability by providing an editing distance between Reeb graphs of orientable surfaces in terms of the cost necessary to transform one graph into another by edit operations. Our main result is that the editing distance between two Reeb graphs is upper bounded by the extent of the difference of the associated functions, measured by the maximum norm. This yields the stability property under function perturbations.