  One of the prevailing ideas in geometric and topological data analysis is to
provide descriptors that encode useful information about hidden objects from
observed data. The Reeb graph is one such descriptor for a given scalar
function. The Reeb graph provides a simple yet meaningful abstraction of the
input domain, and can also be computed efficiently.
  Given the popularity of the Reeb graph in applications, it is important to
understand its stability and robustness with respect to changes in the input
function, as well as to be able to compare the Reeb graphs resulting from
different functions.
  In this paper, we propose a metric for Reeb graphs, called the functional
distortion distance. Under this distance measure, 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 (and thus more discriminative than) 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.
