2026-08-16T06:48:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8404 2024-03-06T10:41:55Z ddc:004 open_access

Maintaining Reeb Graphs of Triangulated 2-Manifolds Agarwal, Pankaj K. Fox, Kyle Nath, Abhinandan Reeb graphs 2-manifolds topological graph theory Let M be a triangulated, orientable 2-manifold of genus g without boundary, and let h be a height function over M that is linear within each triangle. We present a kinetic data structure (KDS) for maintaining the Reeb graph R of h as the heights of M's vertices vary continuously with time. Assuming the heights of two vertices of M become equal only O(1) times, the KDS processes O((k + g) n \polylog n) events; n is the number of vertices in M, and k is the number of external events which change the combinatorial structure of R. Each event is processed in O(\log^2 n) time, and the total size of our KDS is O(gn). The KDS can be extended to maintain an augmented Reeb graph as well. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pankaj K. Agarwal and Kyle Fox and Abhinandan Nath 2018 Is Part Of LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2017.8 urn:nbn:de:0030-drops-84043 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.8 eng https://creativecommons.org/licenses/by/3.0/legalcode