Quasi-Universality of Reeb Graph Distances

Ulrich Bauer, Havard Bakke Bjerkevik, Benedikt Fluhr

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review


We establish bi-Lipschitz bounds certifying quasi-universality (universality up to a constant factor) for various distances between Reeb graphs: the interleaving distance, the functional distortion distance, and the functional contortion distance. The definition of the latter distance is a novel contribution, and for the special case of contour trees we also prove strict universality of this distance. Furthermore, we prove that for the special case of merge trees the functional contortion distance coincides with the interleaving distance, yielding universality of all four distances in this case.
Original languageEnglish
Title of host publication38th International Symposium on Computational Geometry (SoCG 2022)
EditorsXavier Goaoc, Michael Kerber
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Electronic) 978-3-95977-227-3
Publication statusPublished - 1 Jun 2022
Event38th International Symposium on Computational Geometry: SoCG 2022 - Berlin, Germany, Berlin, Germany
Duration: 7 Jun 202210 Jun 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference38th International Symposium on Computational Geometry
Abbreviated titleSoCG 2022
Internet address


  • contour trees
  • distances
  • functional contortion distance
  • functional distortion distance
  • interleaving distance
  • merge trees
  • Reeb graphs
  • universality

ASJC Scopus subject areas

  • Software

Fields of Expertise

  • Information, Communication & Computing

Cite this