The Reeb graph edit distance is universal

DOI10.1007/S10208-020-09488-3MaRDI QIDQ2052722zbMATH OpenOpenAlexFDO

Authors Ulrich Bauer, Facundo Mémoli, C. Landi

Publication date 26 November 2021

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1801.01866

zbMATH Keywords

edit distancequotient metricReeb graphsstability

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Metric spaces, metrizability (54E35) Persistent homology and applications, topological data analysis (55N31)

Abstract: We consider the setting of Reeb graphs of piecewise linear functions and study distances between them that are stable, meaning that functions which are similar in the supremum norm ought to have similar Reeb graphs. We define an edit distance for Reeb graphs and prove that it is stable and universal, meaning that it provides an upper bound to any other stable distance. In contrast, via a specific construction, we show that the interleaving distance and the functional distortion distance on Reeb graphs are not universal.

Recommendations

• The edit distance for Reeb graphs of surfaces
• Measuring distance between Reeb graphs (extended abstract)
• Stable shape comparison of surfaces via Reeb graphs
• Reeb graphs of curves are stable under function perturbations
• Categorified Reeb graphs

Cites work

• Categorified Reeb graphs
• Distances between datasets
• FPT-algorithms for computing Gromov-Hausdorff and interleaving distances between trees
• scientific article; zbMATH DE number 475456 (Why is no real title available?)
• scientific article; zbMATH DE number 3106699 (Why is no real title available?)
• Measuring distance between Reeb graphs (extended abstract)
• Natural pseudo-distance and optimal matching between reduced size functions
• Natural pseudodistances between closed manifolds
• Nilpotent types and fracture squares in homotopy type theory
• On intrinsic geometry of surfaces in normed spaces
• Parametrized complexity theory.
• Reeb graphs of curves are stable under function perturbations
• Stability of persistence diagrams
• Strong equivalence of the interleaving and functional distortion metrics for Reeb graphs
• The edit distance for Reeb graphs of surfaces
• The natural pseudo-distance as a quotient pseudo-metric, and applications
• The theory of the interleaving distance on multidimensional persistence modules

Cited in

(18)

• Generalized persistence diagrams for persistence modules over posets
• Universality of persistence diagrams and the bottleneck and Wasserstein distances
• The edit distance for Reeb graphs of surfaces
• Reeb graphs of curves are stable under function perturbations
• Stable shape comparison of surfaces via Reeb graphs
• Local equivalence and intrinsic metrics between Reeb graphs
• Measuring distance between Reeb graphs (extended abstract)
• Edit Distance and Persistence Diagrams over Lattices
• FPT-algorithms for computing Gromov-Hausdorff and interleaving distances between trees
• Strong equivalence of the interleaving and functional distortion metrics for Reeb graphs
• Distances and isomorphism between networks: stability and convergence of network invariants
• Realizable piecewise linear paths of persistence diagrams with Reeb graphs
• Universal distances for extended persistence
• Classical multidimensional scaling on metric measure spaces
• Labeled interleaving distance for Reeb graphs
• Measure-theoretic Reeb graphs and Reeb spaces
• Tight quasi-universality of Reeb graph distances
• Intrinsic interleaving distance for merge trees

This page was built for publication: The Reeb graph edit distance is universal

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2052722)