{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T16:05:35Z","timestamp":1772553935039,"version":"3.50.1"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2007,7,29]],"date-time":"2007-07-29T00:00:00Z","timestamp":1185667200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2007,7,29]]},"abstract":"<jats:p>Reeb graphs are a fundamental data structure for understanding and representing the topology of shapes. They are used in computer graphics, solid modeling, and visualization for applications ranging from the computation of similarities and finding defects in complex models to the automatic selection of visualization parameters.<\/jats:p>\n          <jats:p>\n            We introduce an\n            <jats:italic>on-line<\/jats:italic>\n            algorithm that reads a stream of elements (vertices, triangles, tetrahedra, etc.) and continuously maintains the Reeb graph of all elements already reed. The algorithm is\n            <jats:italic>robust<\/jats:italic>\n            in handling non-manifold meshes and\n            <jats:italic>general<\/jats:italic>\n            in its applicability to input models of any dimension.\n          <\/jats:p>\n          <jats:p>Optionally, we construct a skeleton-like embedding of the Reeb graph, and\/or remove topological noise to reduce the output size.<\/jats:p>\n          <jats:p>For interactive multi-resolution navigation we also build a hierarchical data structure which allows real-time extraction of approximated Reeb graphs containing all topological features above a given error threshold.<\/jats:p>\n          <jats:p>Our extensive experiments show both high performance and practical linear scalability for meshes ranging from thousands to hundreds of millions of triangles. We apply our algorithm to the largest, most general, triangulated surfaces available to us, including 3D, 4D and 5D simplicial meshes. To demonstrate one important application we use Reeb graphs to find and highlight topological defects in meshes, including some widely believed to be \"clean.\"<\/jats:p>","DOI":"10.1145\/1276377.1276449","type":"journal-article","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T13:44:55Z","timestamp":1189777495000},"page":"58","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":163,"title":["Robust on-line computation of Reeb graphs"],"prefix":"10.1145","volume":"26","author":[{"given":"Valerio","family":"Pascucci","sequence":"first","affiliation":[{"name":"CASC - LLNL\/CS-UC DAVIS"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giorgio","family":"Scorzelli","sequence":"additional","affiliation":[{"name":"CASC-LLNL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peer-Timo","family":"Bremer","sequence":"additional","affiliation":[{"name":"CASC-LLNL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ajith","family":"Mascarenhas","sequence":"additional","affiliation":[{"name":"CASC-LLNL"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,7,29]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997871"},{"key":"e_1_2_2_2_1","volume-title":"Proc. of Shape Modeling International, 142--153","author":"Attene M.","unstructured":"Attene , M. , Biasotti , S. , and Spagbuolo , S . 2001. Remeshing techniques for topological analysis . In Proc. of Shape Modeling International, 142--153 . Attene, M., Biasotti, S., and Spagbuolo, S. 2001. Remeshing techniques for topological analysis. In Proc. of Shape Modeling International, 142--153."},{"key":"e_1_2_2_3_1","volume-title":"Proc. of Spring Conf. on Comp. Graph., 175--184","author":"Biasotti S.","unstructured":"Biasotti , S. , Mortara , M. , and Spagnuolo , M . 2000. Surface compression and reconstruction using Reeb graphs and shape analysis . In Proc. of Spring Conf. on Comp. Graph., 175--184 . Biasotti, S., Mortara, M., and Spagnuolo, M. 2000. Surface compression and reconstruction using Reeb graphs and shape analysis. In Proc. of Spring Conf. on Comp. Graph., 175--184."},{"key":"e_1_2_2_4_1","volume-title":"CESCG","author":"Biasotti S.","year":"2001","unstructured":"Biasotti , S. 2001 . Topological techniques for shape understanding. In Central European Seminar on Computer Graphics , CESCG 2001. Biasotti, S. 2001. Topological techniques for shape understanding. In Central European Seminar on Computer Graphics, CESCG 2001."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(02)00093-7"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/VISUAL.2004.96"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.05.002"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/777792.777844"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90034-2"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796607"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1103900.1103916"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/383259.383282"},{"key":"e_1_2_2_13_1","volume-title":"Proceedings of the IEEE Visualization 2005 (VIS'05)","author":"Isenburg M.","unstructured":"Isenburg , M. , and Lindstrom , P . 2005. Streaming meshes . In Proceedings of the IEEE Visualization 2005 (VIS'05) , IEEE Computer Society, 231--238. Isenburg, M., and Lindstrom, P. 2005. Streaming meshes. In Proceedings of the IEEE Visualization 2005 (VIS'05), IEEE Computer Society, 231--238."},{"key":"e_1_2_2_14_1","first-page":"115","article-title":"Streaming compression of tetrahedral volume meshes","volume":"2006","author":"Isenburg M.","year":"2006","unstructured":"Isenburg , M. , Lindstrom , P. , Gumhold , S. , and Shewchuk , J. 2006 . Streaming compression of tetrahedral volume meshes . In Proceedings of Graphics Interface 2006 , 115 -- 121 . Isenburg, M., Lindstrom, P., Gumhold, S., and Shewchuk, J. 2006. Streaming compression of tetrahedral volume meshes. In Proceedings of Graphics Interface 2006, 115--121.","journal-title":"Proceedings of Graphics Interface"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/304012.304025"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015769"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1052-3"},{"key":"e_1_2_2_18_1","first-page":"847","article-title":"Sur les points singuliers d'une forme de pfaff completement intergrable ou d'une fonction numerique {on the singular points of a complete integral pfaff form or of a numerical function}","volume":"222","author":"Reeb G.","year":"1946","unstructured":"Reeb , G. 1946 . Sur les points singuliers d'une forme de pfaff completement intergrable ou d'une fonction numerique {on the singular points of a complete integral pfaff form or of a numerical function} . Comptes Rendus Acad. Science Paris 222 , 847 -- 849 . Reeb, G. 1946. Sur les points singuliers d'une forme de pfaff completement intergrable ou d'une fonction numerique {on the singular points of a complete integral pfaff form or of a numerical function}. Comptes Rendus Acad. Science Paris 222, 847--849.","journal-title":"Comptes Rendus Acad. Science Paris"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/38.103393"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/38.90568"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/376957.376994"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/566282.566330"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/267734.267760"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/262839.269238"},{"key":"e_1_2_2_25_1","volume-title":"Proc. IEEE Visualization '02","author":"Weber G.","unstructured":"Weber , G. , Scheuermann , G. , Hagen , H. , and Hamann , B . 2002. Exploring scalar fields using critical isovalues . In Proc. IEEE Visualization '02 , IEEE Computer Society Press, IEEE, 171--178. Weber, G., Scheuermann, G., Hagen, H., and Hamann, B. 2002. Exploring scalar fields using critical isovalues. In Proc. IEEE Visualization '02, IEEE Computer Society Press, IEEE, 171--178."},{"key":"e_1_2_2_26_1","volume-title":"Proc. IEEE Visualization '00","author":"Wood Z. J.","unstructured":"Wood , Z. J. , Desbrun , M. , Schroder , P. , and Breen , D. E . 2000. Semi-regular mesh extraction from volumes . In Proc. IEEE Visualization '00 , IEEE Computer Society Press, Los Alamitos California, 275--282. Wood, Z. J., Desbrun, M., Schroder, P., and Breen, D. E. 2000. Semi-regular mesh extraction from volumes. In Proc. IEEE Visualization '00, IEEE Computer Society Press, Los Alamitos California, 275--282."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/990002.990007"},{"key":"e_1_2_2_28_1","volume-title":"Proc. Graph. Interf., 185--192","author":"Wu J.","unstructured":"Wu , J. , and Kobbelt , L . 2003. A stream algorithm for the decimation of massive meshes . In Proc. Graph. Interf., 185--192 . Wu, J., and Kobbelt, L. 2003. A stream algorithm for the decimation of massive meshes. In Proc. Graph. Interf., 185--192."}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1276377.1276449","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1276377.1276449","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:52:18Z","timestamp":1750258338000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1276377.1276449"}},"subtitle":["simplicity and speed"],"short-title":[],"issued":{"date-parts":[[2007,7,29]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,7,29]]}},"alternative-id":["10.1145\/1276377.1276449"],"URL":"https:\/\/doi.org\/10.1145\/1276377.1276449","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,7,29]]},"assertion":[{"value":"2007-07-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}