text: Metric graphs are meaningful objects for modeling complex structures that arise in many real-world applications, such as road networks, river systems, earthquake faults, blood vessels, and filamentary structures in galaxies. To study metric graphs in the context of comparison, we are interested in determining the relative discriminative capabilities of two topology-based distances between a pair of arbitrary finite metric graphs: the persistence distortion distance and the intrinsic Cech distance. We explicitly show how to compute the intrinsic Cech distance between two metric graphs based solely on knowledge of the shortest systems of loops for the graphs. Our main theorem establishes an inequality between the intrinsic Cech and persistence distortion distances in the case when one of the graphs is a bouquet graph and the other is arbitrary. The relationship also holds when both graphs are constructed via wedge sums of cycles and edges.
  @cite_13: 
  @cite_18: 
  @cite_26: 
  @cite_6: Metric graphs are ubiquitous in science and engineering. For example, many data are drawn from hidden spaces that are graph-like, such as the cosmic web. A metric graph offers one of the simplest yet still meaningful ways to represent the non-linear structure hidden behind the data. In this paper, we propose a new distance between two finite metric graphs, called the persistence-distortion distance, which draws upon a topological idea. This topological perspective along with the metric space viewpoint provide a new angle to the graph matching problem. Our persistence-distortion distance has two properties not shared by previous methods: First, it is stable against the perturbations of the input graph metrics. Second, it is a continuous distance measure, in the sense that it is defined on an alignment of the underlying spaces of input graphs, instead of merely their nodes. This makes our persistence-distortion distance robust against, for example, different discretizations of the same underlying graph. Despite considering the input graphs as continuous spaces, that is, taking all points into account, we show that we can compute the persistence-distortion distance in polynomial time. The time complexity for the discrete case where only graph nodes are considered is much faster.
  @cite_3: 
  @cite_24: Reeb graphs are structural descriptors that capture shape properties of a topological space from the perspective of a chosen function. In this work, we define a combinatorial distance for Reeb graphs of orientable surfaces in terms of the cost necessary to transform one graph into another by edit operations. The main contributions of this paper are the stability property and the optimality of this edit distance. More precisely, the stability result states that changes in the Reeb graphs, measured by the edit distance, are as small as changes in the functions, measured by the maximum norm. The optimality result states that the edit distance discriminates Reeb graphs better than any other distance for Reeb graphs of surfaces satisfying the stability property.
  @cite_5: 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.
  @cite_16: A standard result in metric geometry is that every compact geodesic metric space can be approximated arbitrarily well by finite metric graphs in the Gromov-Hausdorff sense. It is well known that the first Betti number of the approximating graphs may blow up as the approximation gets finer. In our work, given a compact geodesic metric space @math , we define a sequence @math of non-negative real numbers by @math By construction, and the above result, this is a non-increasing sequence with limit @math . We study this sequence and its rates of decay with @math . We also identify a precise relationship between the sequence and the first Vietoris-Rips persistence barcode of @math . Furthermore, we specifically analyze @math and find upper and lower bounds based on hyperbolicity and other metric invariants. As a consequence of the tools we develop, our work also provides a Gromov-Hausdorff stability result for the Reeb construction on geodesic metric spaces with respect to the function given by distance to a reference point.
  @cite_10: Stable topological invariants are a cornerstone of persistence theory and applied topology, but their discriminative properties are often poorly-understood. In this paper we investigate the injectivity of a rich homology-based invariant first defined in dey2015comparing which we think of as embedding a metric graph in the barcode space.
summary: Recently, several distances for comparing metric graphs have been proposed based on ideas from computational topology. In the case of a special type of metric graph called a Reeb graph, these distances include: the functional distortion distance @cite_5 , the combinatorial edit distance @cite_24 , the interleaving distance @cite_3 , and its variant in the setting of merge trees @cite_26 . In particular, the functional distortion distance can be considered as a variation of the Gromov-Hausdorff distance between two metric spaces @cite_5 . The interleaving distance is defined via algebraic topology and utilizes the equivalence between Reeb graphs and cosheaves @cite_3 . For metric graphs in general, both the persistence distortion distance @cite_6 and the intrinsic distance @cite_18 take into consideration the structure of metric graphs, independent of their geometric embeddings, by treating them as continuous metric spaces. In @cite_10 , Oudot and Solomon point out that since compact geodesic spaces can be approximated by finite metric graphs in the Gromov--Hausdorff sense @cite_13 (see also the recent work of M 'emoli and Okutan @cite_16 ), one can study potentially complicated length spaces by studying the persistence distortion of a sequence of approximating graphs.