Efficient algorithms for computing Reeb graphs

Auber, 2003, Tulip: A huge graph visualisation framework, 105 C.L. Bajaj, V. Pascucci, D.R. Schikore, The contour spectrum, in: Proc. IEEE Conf. Visualization, 1997, pp. 167–173 Banchoff, 1970, Critical points and curvature for embedded polyhedral surfaces, Am. Math. Monthly, 77, 475, 10.2307/2317380 Bent, 1985, Biased search trees, SIAM J. Comput., 14, 545, 10.1137/0214041 Carr, 2003, Computing contour trees in all dimensions, Comput. Geom. Theory Appl., 24, 75, 10.1016/S0925-7721(02)00093-7 H. Carr, J. Snoeyink, M. van de Panne, Simplifying flexible isosurfaces using local geometric measures, in: Proc. IEEE Conf. Visualization, 2004, pp. 497–504 Cole-McLaughlin, 2004, Loops in Reeb graphs of 2-manifolds, Discrete Comput. Geom., 32, 231, 10.1007/s00454-004-1122-6 Cormen, 2001 H. Edelsbrunner, J. Harer, V. Natarajan, V. Pascucci, Morse–Smale complexes for piecewise linear 3-manifolds, in: Proc. 19th Annual Symposium on Computational Geometry, 2003, pp. 361–370 D. Eppstein, Dynamic generators of topologically embedded graphs, in: SODA '03: Proc. Fourteenth Annual ACM–SIAM Symposium on Discrete Algorithms, 2003, pp. 599–608 Eppstein, 1992, Maintenance of a minimum spanning forest in a dynamic plane graph, J. Algorithms, 13, 33, 10.1016/0196-6774(92)90004-V I. Guskov, Z. Wood, Topological noise removal, in: Proc. Graphics Interface, 2001, pp. 19–26 Hétroy, 2003, Topological quadrangulations of closed triangulated surfaces using the Reeb graph, Graph. Models, 65, 131, 10.1016/S1524-0703(03)00005-5 M. Hilaga, Y. Shinagawa, T. Kohmura, T.L. Kunii, Topology matching for fully automatic similarity estimation of 3d shapes, in: Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, 2001, pp. 203–212 Holm, 2001, Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, J. ACM, 48, 723, 10.1145/502090.502095 E.P. Mücke, Shapes and implementations in three-dimensional geometry, PhD thesis, Dept. Computer Science, University of Illinois, Urbana-Champaign, Illinois, 1993 Pascucci, 2003, Parallel computation of the topology of level sets, Algorithmica, 38, 249, 10.1007/s00453-003-1052-3 Pascucci, 2007, Robust on-line computation of reeb graphs: simplicity and speed, ACM Trans. Graph., 26, 58, 10.1145/1276377.1276449 Reeb, 1946, Sur les points singuliers d'une forme de Pfaff complètement intégrable ou d'une fonction numérique, C. R. Acad. Sci. Paris, 222, 847 Shinagawa, 1991, Constructing a Reeb graph automatically from cross sections, IEEE Comput. Graph. Appl., 11, 44, 10.1109/38.103393 Shinagawa, 1991, Surface coding based on Morse theory, IEEE Comput. Graph. Appl., 11, 66, 10.1109/38.90568 Sleator, 1983, A data structure for dynamic trees, J. Comput. Syst. Sci., 26, 362, 10.1016/0022-0000(83)90006-5 M. Thorup, Near-optimal fully-dynamic graph connectivity, in: STOC '00: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000, pp. 343–350 T. Tung, F. Schmitt, Augmented Reeb graphs for content-based retrieval of 3d mesh models, in: SMI '04: Proceedings of the Shape Modeling International 2004 (SMI'04), 2004, pp. 157–166 M. van Kreveld, R. van Oostrum, C. Bajaj, V. Pascucci, D.R. Schikore, Contour trees and small seed sets for isosurface traversal, in: Proceedings of the 13th ACM Annual Symposium on Computational Geometry, 1997, pp. 212–220 Weber, 2007, Topology-controlled volume rendering, IEEE Trans. Vis. Comput. Graph., 13, 330, 10.1109/TVCG.2007.47 Wood, 2004, Removing excess topology from isosurfaces, ACM Trans. Graph., 23, 190, 10.1145/990002.990007 Shinagawa, 1995, Modeling contact of two complex objects: With an application to characterizing dental articulations, Computers and Graphics, 19, 21, 10.1016/0097-8493(94)00118-I Zhang, 2005, Feature-based surface parameterization and texture mapping, ACM Trans. Graph., 24, 1, 10.1145/1037957.1037958