{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T22:11:47Z","timestamp":1768428707907,"version":"3.49.0"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2020,12,29]],"date-time":"2020-12-29T00:00:00Z","timestamp":1609200000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,12,29]],"date-time":"2020-12-29T00:00:00Z","timestamp":1609200000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005713","name":"Technische Universit\u00e4t M\u00fcnchen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005713","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2021,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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.<\/jats:p>","DOI":"10.1007\/s10208-020-09488-3","type":"journal-article","created":{"date-parts":[[2020,12,29]],"date-time":"2020-12-29T07:02:33Z","timestamp":1609225353000},"page":"1441-1464","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["The Reeb Graph Edit Distance is Universal"],"prefix":"10.1007","volume":"21","author":[{"given":"Ulrich","family":"Bauer","sequence":"first","affiliation":[]},{"given":"Claudia","family":"Landi","sequence":"additional","affiliation":[]},{"given":"Facundo","family":"M\u00e9moli","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,12,29]]},"reference":[{"key":"9488_CR1","doi-asserted-by":"publisher","unstructured":"Ulrich Bauer, Barbara Di\u00a0Fabio, and Claudia Landi. An Edit Distance for Reeb Graphs. In Eurographics Workshop on 3D Object Retrieval. The Eurographics Association, 2016. https:\/\/doi.org\/10.2312\/3dor.20161084.","DOI":"10.2312\/3dor.20161084"},{"key":"9488_CR2","doi-asserted-by":"publisher","unstructured":"Ulrich Bauer, Xiaoyin Ge, and Yusu Wang. Measuring distance between Reeb graphs. In Proceedings of the Thirtieth Annual Symposium on Computational Geometry, SoCG\u201914, New York, NY, USA, 2014. ACM. https:\/\/doi.org\/10.1145\/2582112.2582169.","DOI":"10.1145\/2582112.2582169"},{"key":"9488_CR3","doi-asserted-by":"publisher","unstructured":"Ulrich Bauer, Elizabeth Munch, and Yusu Wang. Strong equivalence of the interleaving and functional distortion metrics for Reeb graphs. In 31st International Symposium on Computational Geometry (SoCG 2015), Leibniz International Proceedings in Informatics (LIPIcs), pages 461\u2013475, Dagstuhl, Germany, 2015. https:\/\/doi.org\/10.4230\/LIPIcs.SOCG.2015.461.","DOI":"10.4230\/LIPIcs.SOCG.2015.461"},{"key":"9488_CR4","doi-asserted-by":"crossref","unstructured":"Dmitri Burago, Iu\u00a0D Burago, Yuri Burago, Sergei Ivanov, and Sergei\u00a0A Ivanov. A course in metric geometry, volume\u00a033. American Mathematical Soc., 2001.","DOI":"10.1090\/gsm\/033"},{"issue":"3","key":"9488_CR5","doi-asserted-by":"publisher","first-page":"1729","DOI":"10.1515\/forum-2012-0152","volume":"27","author":"Francesca Cagliari","year":"2015","unstructured":"Francesca Cagliari, Barbara Di\u00a0Fabio, and Claudia Landi. The natural pseudo-distance as a quotient pseudo-metric, and applications. Forum Math., 27(3):1729\u20131742, 2015. https:\/\/doi.org\/10.1515\/forum-2012-0152.","journal-title":"Forum Math."},{"issue":"1","key":"9488_CR6","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/s00454-006-1276-5","volume":"37","author":"David Cohen-Steiner","year":"2007","unstructured":"David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Stability of persistence diagrams. Discrete Comput. Geom., 37(1):103\u2013120, 2007. https:\/\/doi.org\/10.1007\/s00454-006-1276-5.","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"9488_CR7","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1007\/s10440-008-9332-1","volume":"109","author":"Michele d\u2019Amico","year":"2010","unstructured":"Michele d\u2019Amico, Patrizio Frosini, and Claudia Landi. Natural pseudo-distance and optimal matching between reduced size functions. Acta Applicandae Mathematicae, 109(2):527\u2013554, 2010. https:\/\/doi.org\/10.1007\/s10440-008-9332-1.","journal-title":"Acta Applicandae Mathematicae"},{"issue":"4","key":"9488_CR8","doi-asserted-by":"publisher","first-page":"854","DOI":"10.1007\/s00454-016-9763-9","volume":"55","author":"Vin de Silva","year":"2016","unstructured":"Vin de\u00a0Silva, Elizabeth Munch, and Amit Patel. Categorified Reeb graphs. Discrete & Computational Geometry, 55(4):854\u2013906, 2016. https:\/\/doi.org\/10.1007\/s00454-016-9763-9.","journal-title":"Discrete & Computational Geometry"},{"issue":"2","key":"9488_CR9","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/s00454-016-9758-6","volume":"55","author":"Barbara Di Fabio","year":"2016","unstructured":"Barbara Di\u00a0Fabio and Claudia Landi. The edit distance for Reeb graphs of surfaces. Discrete & Computational Geometry, 55(2):423\u2013461, 2016. https:\/\/doi.org\/10.1007\/s00454-016-9758-6.","journal-title":"Discrete & Computational Geometry"},{"issue":"5","key":"9488_CR10","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1515\/form.2004.032","volume":"16","author":"Pietro Donatini","year":"2004","unstructured":"Pietro Donatini and Patrizio Frosini. Natural pseudodistances between closed manifolds. Forum Math., 16(5):695\u2013715, 2004. https:\/\/doi.org\/10.1515\/form.2004.032.","journal-title":"Forum Math."},{"issue":"12","key":"9488_CR11","doi-asserted-by":"publisher","first-page":"1456","DOI":"10.1002\/mma.2533","volume":"35","author":"Barbara Di Fabio","year":"2012","unstructured":"Barbara\u00a0Di Fabio and Claudia Landi. Reeb graphs of curves are stable under function perturbations. Mathematical Methods in the Applied Sciences, 35(12):1456\u20131471, 2012. https:\/\/doi.org\/10.1002\/mma.2533.","journal-title":"Mathematical Methods in the Applied Sciences"},{"key":"9488_CR12","unstructured":"J\u00f6rg Flum and Martin Grohe. Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer-Verlag, Berlin, Heidelberg, 2006."},{"key":"9488_CR13","doi-asserted-by":"publisher","unstructured":"Masaki Hilaga, Yoshihisa Shinagawa, Taku Kohmura, and Tosiyasu\u00a0L. Kunii. Topology matching for fully automatic similarity estimation of 3D shapes. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques, SIGGRAPH \u201901, pages 203\u2013212. ACM Press, 2001. https:\/\/doi.org\/10.1145\/383259.383282.","DOI":"10.1145\/383259.383282"},{"issue":"3","key":"9488_CR14","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/s10208-015-9255-y","volume":"15","author":"Michael Lesnick","year":"2015","unstructured":"Michael Lesnick. The theory of the interleaving distance on multidimensional persistence modules. Foundations of Computational Mathematics, 15(3):613\u2013650, 2015. https:\/\/doi.org\/10.1007\/s10208-015-9255-y.","journal-title":"Foundations of Computational Mathematics"},{"key":"9488_CR15","unstructured":"Facundo M\u00e9moli. A distance between filtered spaces via tripods. Preprint, 2017. arXiv:1704.03965."},{"key":"9488_CR16","first-page":"847","volume":"222","author":"Georges Reeb","year":"1946","unstructured":"Georges Reeb. Sur les points singuliers d\u2019une forme de Pfaff compl\u00e9tement int\u00e9grable ou d\u2019une fonction num\u00e9rique. Comptes Rendus de L\u2019Acad\u00e9mie des Sciences, 222:847\u2013849, 1946.","journal-title":"Comptes Rendus de L\u2019Acad\u00e9mie des Sciences"},{"key":"9488_CR17","unstructured":"Luis\u00a0N Scoccola. Locally Persistent Categories And Metric Properties Of Interleaving Distances. PhD thesis, University of Western Ontario, 2020."},{"issue":"6","key":"9488_CR18","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1109\/38.103393","volume":"11","author":"Yoshihisa Shinagawa","year":"1991","unstructured":"Yoshihisa Shinagawa and Tosiyasu\u00a0L. Kunii. Constructing a Reeb graph automatically from cross sections. IEEE Computer Graphics and Applications, 11(6):44\u201351, 1991. https:\/\/doi.org\/10.1109\/38.103393.","journal-title":"IEEE Computer Graphics and Applications"},{"key":"9488_CR19","doi-asserted-by":"publisher","unstructured":"Gurjeet Singh, Facundo M\u00e9moli, and Gunnar Carlsson. Topological Methods for the Analysis of High Dimensional Data Sets and 3D Object Recognition. In Eurographics Symposium on Point-Based Graphics. The Eurographics Association, 2007. https:\/\/doi.org\/10.2312\/SPBG\/SPBG07\/091-100.","DOI":"10.2312\/SPBG\/SPBG07\/091-100"},{"key":"9488_CR20","doi-asserted-by":"publisher","unstructured":"John\u00a0R. Stallings. Brick\u2019s Quasi Simple Filtrations and 3-Manifolds, volume 188 of London Mathematical Society Lecture Note Series, page 188\u2013203. Cambridge University Press, 1993. https:\/\/doi.org\/10.1017\/CBO9780511661860.017.","DOI":"10.1017\/CBO9780511661860.017"},{"key":"9488_CR21","doi-asserted-by":"publisher","unstructured":"Elena\u00a0Farahbakhsh Touli and Yusu Wang. FPT-algorithms for computing Gromov\u2013Hausdorff and interleaving distances between trees. In Michael\u00a0A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich\/Garching, Germany, volume 144 of LIPIcs, pages 83:1\u201383:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2019. https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.83.","DOI":"10.4230\/LIPIcs.ESA.2019.83"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-020-09488-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10208-020-09488-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-020-09488-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,13]],"date-time":"2021-10-13T03:22:32Z","timestamp":1634095352000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10208-020-09488-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,29]]},"references-count":21,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["9488"],"URL":"https:\/\/doi.org\/10.1007\/s10208-020-09488-3","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,29]]},"assertion":[{"value":"28 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 September 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 October 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 December 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}