{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:34:03Z","timestamp":1750221243650,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,8,21]],"date-time":"2018-08-21T00:00:00Z","timestamp":1534809600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Advanced Grant of the European Research Council GUDHI"},{"name":"Irit Dinur's ERC-StG","award":["239985"],"award-info":[{"award-number":["239985"]}]},{"name":"ERC-CoG","award":["772839"],"award-info":[{"award-number":["772839"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2018,10,31]]},"abstract":"<jats:p>\n            A filtration over a simplicial complex\n            <jats:italic>K<\/jats:italic>\n            is an ordering of the simplices of\n            <jats:italic>K<\/jats:italic>\n            such that all prefixes in the ordering are subcomplexes of\n            <jats:italic>K<\/jats:italic>\n            . Filtrations are at the core of Persistent Homology, a major tool in Topological Data Analysis. To represent the filtration of a simplicial complex, the entire filtration can be appended to any data structure that explicitly stores all the simplices of the complex such as the Hasse diagram or the recently introduced Simplex Tree [Algorithmica\u201914]. However, with the popularity of various computational methods that need to handle simplicial complexes, and with the rapidly increasing size of the complexes, the task of finding a compact data structure that can still support efficient queries is of great interest.\n          <\/jats:p>\n          <jats:p>\n            This direction has been recently pursued for the case of maintaining simplicial complexes. For instance, Boissonnat et al. [Algorithmica\u201917] considered storing the simplices that are maximal with respect to inclusion and Attali et al. [IJCGA\u201912] considered storing the simplices that block the expansion of the complex. Nevertheless, so far there has been no data structure that compactly stores the\n            <jats:italic>filtration<\/jats:italic>\n            of a simplicial complex, while also allowing the efficient implementation of basic operations on the complex.\n          <\/jats:p>\n          <jats:p>In this article, we propose a new data structure called the Critical Simplex Diagram (CSD), which is a variant of the Simplex Array List [Algorithmica\u201917]. Our data structure allows one to store in a compact way the filtration of a simplicial complex and allows for the efficient implementation of a large range of basic operations. Moreover, we prove that our data structure is essentially optimal with respect to the requisite storage space. Finally, we show that the CSD representation admits fast construction algorithms for Flag complexes and relaxed Delaunay complexes.<\/jats:p>","DOI":"10.1145\/3229146","type":"journal-article","created":{"date-parts":[[2018,8,21]],"date-time":"2018-08-21T12:09:47Z","timestamp":1534853387000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["An Efficient Representation for Filtrations of Simplicial Complexes"],"prefix":"10.1145","volume":"14","author":[{"given":"Jean-Daniel","family":"Boissonnat","sequence":"first","affiliation":[{"name":"INRIA Sophia-Antipolis, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9105-364X","authenticated-orcid":false,"given":"Karthik","family":"C. S.","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,8,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195912600060"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_50"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0207-y"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9887-3"},{"key":"e_1_2_1_5_1","unstructured":"Jean-Daniel Boissonnat and Fran\u00e7ois Godi. 2018. Representation of simplicial complexes: A comparative study. (unpublished)"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 26th Annual European Symposium on Algorithms (ESA'18)","author":"Boissonnat Jean-Daniel","year":"2018","unstructured":"Jean-Daniel Boissonnat, Siddharth Pritam, and Divyansh Pareek. 2018. Strong Collapse for Persistence. In Proceedings of the 26th Annual European Symposium on Algorithms (ESA'18). Helsinki Finland."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542362.1542407"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10711-008-9261-1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2582112.2582165"},{"key":"e_1_2_1_10_1","first-page":"91","article-title":"Some new results on circle graphs","volume":"25","author":"Dur\u00e1n Guillermo","year":"2003","unstructured":"Guillermo Dur\u00e1n. 2003. Some new results on circle graphs. Mat. Contemp. 25 (2003), 91--106.","journal-title":"Mat. Contemp."},{"volume-title":"Computational Topology\u2014An Introduction","author":"Edelsbrunner Herbert","key":"e_1_2_1_11_1","unstructured":"Herbert Edelsbrunner and John Harer. 2010. Computational Topology\u2014An Introduction. American Mathematical Society."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17517-6_36"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230040407"},{"key":"e_1_2_1_15_1","unstructured":"M. Glisse and S. Sivaprasad. 2016. Private communication."},{"volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic Martin Charles","key":"e_1_2_1_16_1","unstructured":"Martin Charles Golumbic. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201913)","author":"Grohe Martin","year":"2013","unstructured":"Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. 2013. Characterisations of nowhere dense graphs (invited talk). In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201913). 21--40."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(73)80009-7"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27810-8_23"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 7th Quadrennial International Conference on the Theory and Applications of Graphs, Graph Theory, Combinatorics, and Applications. 945--956","author":"Prisner Erich","year":"1995","unstructured":"Erich Prisner. 1995. Graphs with few cliques. In Proceedings of the 7th Quadrennial International Conference on the Theory and Applications of Graphs, Graph Theory, Combinatorics, and Applications. 945--956."},{"key":"e_1_2_1_21_1","unstructured":"The GUDHI Project. 2015. GUDHI User and Reference Manual. GUDHI Editorial Board."},{"key":"e_1_2_1_22_1","volume-title":"Complexity results on graphs with few cliques. Discr. Math. Theor. Comput. Sci. 9, 1","author":"Rosgen Bill","year":"2007","unstructured":"Bill Rosgen and Lorna Stewart. 2007. Complexity results on graphs with few cliques. Discr. Math. Theor. Comput. Sci. 9, 1 (2007)."},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"J. P. Spinrad. 2003. Efficient Graph Representations: The Fields Institute for Research in Mathematical Sciences. American Mathematical Soc.","DOI":"10.1090\/fim\/019"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3229146","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3229146","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:35Z","timestamp":1750212455000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3229146"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,21]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,10,31]]}},"alternative-id":["10.1145\/3229146"],"URL":"https:\/\/doi.org\/10.1145\/3229146","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2018,8,21]]},"assertion":[{"value":"2016-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}