{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:36:46Z","timestamp":1750307806519,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":54,"publisher":"ACM","license":[{"start":{"date-parts":[[2008,6,9]],"date-time":"2008-06-09T00:00:00Z","timestamp":1212969600000},"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":[],"published-print":{"date-parts":[[2008,6,9]]},"DOI":"10.1145\/1377676.1377721","type":"proceedings-article","created":{"date-parts":[[2008,6,10]],"date-time":"2008-06-10T14:13:22Z","timestamp":1213107202000},"page":"251-259","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Testing contractibility in planar rips complexes"],"prefix":"10.1145","author":[{"given":"Erin W.","family":"Chambers","sequence":"first","affiliation":[{"name":"UIUC, Urbana, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeff","family":"Erickson","sequence":"additional","affiliation":[{"name":"UIUC, Urbana, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pratik","family":"Worah","sequence":"additional","affiliation":[{"name":"UIUC, Urbana, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"The LCA problem revisited. phProc 4th Latin American Symp. Theoret. Informatics (LATIN), 88--94","author":"Bender M. A.","year":"2000","unstructured":"M. A. Bender and M. Farach-Colton . The LCA problem revisited. phProc 4th Latin American Symp. Theoret. Informatics (LATIN), 88--94 , 2000 . M. A. Bender and M. Farach-Colton. The LCA problem revisited. phProc 4th Latin American Symp. Theoret. Informatics (LATIN), 88--94, 2000."},{"key":"e_1_3_2_1_2_1","volume-title":"Computing homotopic shortest paths in the plane. phProc. 14th Annu. ACM--SIAM Sympos. Discrete Algorithms, 609--617","author":"Bespamyatnikh S.","year":"2003","unstructured":"S. Bespamyatnikh . Computing homotopic shortest paths in the plane. phProc. 14th Annu. ACM--SIAM Sympos. Discrete Algorithms, 609--617 , 2003 . S. Bespamyatnikh. Computing homotopic shortest paths in the plane. phProc. 14th Annu. ACM--SIAM Sympos. Discrete Algorithms, 609--617, 2003."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24698-5_37"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109691"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-003-2949-y"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1292-5"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1142\/S021819590600204X"},{"key":"e_1_3_2_1_8_1","volume-title":"Persistent homology and the analysis of high dimensional data. Presentation at the Symposium on the Geometry of Very Large Data Sets","author":"Carlsson G.","year":"2005","unstructured":"G. Carlsson . Persistent homology and the analysis of high dimensional data. Presentation at the Symposium on the Geometry of Very Large Data Sets , Fields Institute for Research in Mathematical Sciences, February 24, 2005 . http:\/\/comptop.stanford.edu\/preprints\/ottawa.pdf. G. Carlsson. Persistent homology and the analysis of high dimensional data. Presentation at the Symposium on the Geometry of Very Large Data Sets, Fields Institute for Research in Mathematical Sciences, February 24, 2005. http:\/\/comptop.stanford.edu\/preprints\/ottawa.pdf."},{"key":"e_1_3_2_1_9_1","volume-title":"Preprint","author":"Carlsson G.","year":"2006","unstructured":"G. Carlsson , T. Ishkhanov , V. de Silva , and A. Zomorodian . On the local behaevior of spaces of natural images . Preprint , 2006 . G. Carlsson, T. Ishkhanov, V. de Silva, and A. Zomorodian. On the local behaevior of spaces of natural images. Preprint, 2006."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218654305000761"},{"key":"e_1_3_2_1_11_1","volume-title":"18th Ann. ACM-SIAM Symp. Discrete Algorithms, 89--97","author":"Chambers E. W.","year":"2007","unstructured":"E. W. Chambers and S. Cabello . Multiple source shortest paths in a genus g graph. phProc . 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 89--97 , 2007 . E. W. Chambers and S. Cabello. Multiple source shortest paths in a genus g graph. phProc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 89--97, 2007."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137918"},{"key":"e_1_3_2_1_13_1","volume-title":"Preprint","author":"Chambers E. W.","year":"2007","unstructured":"E. W. Chambers , V. de Silva , J. Erickson , and R. Ghrist . Rips complexes of planar point sets . Preprint , 2007 , ArXiv:0712.0395. E. W. Chambers, V. de Silva, J. Erickson, and R. Ghrist. Rips complexes of planar point sets. Preprint, 2007, ArXiv:0712.0395."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/98524.98532"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109580"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-004-1150-2"},{"key":"e_1_3_2_1_17_1","volume-title":"Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 278--287","author":"Demaine E. D.","year":"2007","unstructured":"E. D. Demaine , M. Hajiaghayi , and B. Mohar . Approximation algorithms via contraction decomposition . Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 278--287 , 2007 . E. D. Demaine, M. Hajiaghayi, and B. Mohar. Approximation algorithms via contraction decomposition. Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 278--287, 2007."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1619"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02570697"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054106004315"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574053"},{"key":"e_1_3_2_1_22_1","volume-title":"Cambridge Monographs on Applied and Computational Mathematics","author":"Edelsbrunner H.","year":"2006","unstructured":"H. Edelsbrunner . Geometry and Topology for Mesh Generation . Cambridge Monographs on Applied and Computational Mathematics . Cambridge University Press , New York, NY, USA , 2006 . H. Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, New York, NY, USA, 2006."},{"volume-title":"Persistent homology: A survey. Discrete &amp","author":"Edelsbrunner H.","key":"e_1_3_2_1_23_1","unstructured":"H. Edelsbrunner and J. Harer . Persistent homology: A survey. Discrete &amp ; Computational Topology : Twenty Years Later , to appear. AMS Press. http:\/\/www.cs.duke.edu\/ edels\/BookSurv\/PersistenceSurvey.pdf. H. Edelsbrunner and J. Harer. Persistent homology: A survey. Discrete & Computational Topology: Twenty Years Later, to appear. AMS Press. http:\/\/www.cs.duke.edu\/ edels\/BookSurv\/PersistenceSurvey.pdf."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-002-2885-2"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2006.03.003"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-003-2948-z"},{"key":"e_1_3_2_1_27_1","volume-title":"Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms, 1038--1046","author":"Erickson J.","year":"2005","unstructured":"J. Erickson and K. Whittlesey . Greedy optimal homotopy and homology generators . Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms, 1038--1046 , 2005 . J. Erickson and K. Whittlesey. Greedy optimal homotopy and homology generators. Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms, 1038--1046, 2005."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/367390.367400"},{"key":"e_1_3_2_1_29_1","volume-title":"Preprint","author":"Ghrist R.","year":"2007","unstructured":"R. Ghrist . Barcodes : The persistent topology of data . Preprint , 2007 . http:\/\/www.math.uiuc.edu\/ ghrist\/preprints\/barcodes.pdf. R. Ghrist. Barcodes: The persistent topology of data. Preprint, 2007. http:\/\/www.math.uiuc.edu\/ ghrist\/preprints\/barcodes.pdf."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/1147685.1147729"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/281508.281528"},{"key":"e_1_3_2_1_32_1","volume-title":"Essays in Group Theory, 75--265","author":"Gromov M.","year":"1987","unstructured":"M. Gromov . Hyperbolic groups. Essays in Group Theory, 75--265 , 1987 . MSRI Publications 8, Springer-Verlag . M. Gromov. Hyperbolic groups. Essays in Group Theory, 75--265, 1987. MSRI Publications 8, Springer-Verlag."},{"key":"e_1_3_2_1_33_1","volume-title":"Proc. Graphics Interface, 19--26","author":"Guskov I.","year":"2001","unstructured":"I. Guskov and Z. Wood . Topological noise removal . Proc. Graphics Interface, 19--26 , 2001 . I. Guskov and Z. Wood. Topological noise removal. Proc. Graphics Interface, 19--26, 2001."},{"key":"e_1_3_2_1_34_1","volume-title":"Cambridge University Press","author":"Hatcher A.","year":"2001","unstructured":"A. Hatcher . Algebraic Topology . Cambridge University Press , 2001 . http:\/\/www.math.cornell.edu\/~hatcher\/. A. Hatcher. Algebraic Topology. Cambridge University Press, 2001. http:\/\/www.math.cornell.edu\/~hatcher\/."},{"key":"e_1_3_2_1_35_1","volume-title":"Prospects in Topology: Proceedings of a Conference in Honor of William Browder, 157--188","author":"Hausmann J.-C.","year":"1995","unstructured":"J.-C. Hausmann . On the Vietoris-Rips complexes and a cohomology theory for metric spaces . Prospects in Topology: Proceedings of a Conference in Honor of William Browder, 157--188 , 1995 . Ann. Math. Stud. 138, Princeton Univ. Press. J.-C. Hausmann. On the Vietoris-Rips complexes and a cohomology theory for metric spaces. Prospects in Topology: Proceedings of a Conference in Honor of William Browder, 157--188, 1995. Ann. Math. Stud. 138, Princeton Univ. Press."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(94)90010-8"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1017"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250848"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137919"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00000526"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/378583.378630"},{"key":"e_1_3_2_1_42_1","volume-title":"Proceedings of the International Congress of Mathematics, 14--21","author":"Markov A. A.","year":"1958","unstructured":"A. A. Markov . Insolubility of the problem of homeomorphy . Proceedings of the International Congress of Mathematics, 14--21 , 1958 . Cambridge University Press. A. A. Markov. Insolubility of the problem of homeomorphy. Proceedings of the International Congress of Mathematics, 14--21, 1958. Cambridge University Press."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1991250201031"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"Mohar B.","year":"2001","unstructured":"B. Mohar and C. Thomassen . Graphs on Surfaces . Jons Hopkins Univ. Press , 2001 . B. Mohar and C. Thomassen. Graphs on Surfaces. Jons Hopkins Univ. Press, 2001."},{"volume-title":"Asymptotic stability of switched higher order Laplacians and dynamic coverage","author":"Muhammad A.","key":"e_1_3_2_1_45_1","unstructured":"A. Muhammad and A. Jadbabaie . Asymptotic stability of switched higher order Laplacians and dynamic coverage . Hybrid Systems : Computation and Control , p. to appear, 2007. Lecture Notes Comput. Sci., Springer--Verlag. http:\/\/www.seas.upenn.edu\/~jadbabai\/papers\/Muhammad_Jadbabaie_HSCC07_FinalSubmission.pdf. A. Muhammad and A. Jadbabaie. Asymptotic stability of switched higher order Laplacians and dynamic coverage. Hybrid Systems: Computation and Control, p. to appear, 2007. Lecture Notes Comput. Sci., Springer--Verlag. http:\/\/www.seas.upenn.edu\/~jadbabai\/papers\/Muhammad_Jadbabaie_HSCC07_FinalSubmission.pdf."},{"key":"e_1_3_2_1_46_1","first-page":"2007","volume-title":"Proceedings of Robotics: Science and Systems","author":"Muhammad A.","unstructured":"A. Muhammad and A. Jadbabaie . Dynamic coverage verification in mobile sensor networks via switched higher order Laplacians . Proceedings of Robotics: Science and Systems , p. to appear, 2007 . http:\/\/www.seas.upenn.edu\/ jadbabai\/papers\/RSS_FINAL.pdf. A. Muhammad and A. Jadbabaie. Dynamic coverage verification in mobile sensor networks via switched higher order Laplacians. Proceedings of Robotics: Science and Systems, p. to appear, 2007. http:\/\/www.seas.upenn.edu\/ jadbabai\/papers\/RSS_FINAL.pdf."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-4372-4","volume-title":"Classical Topology and Combinatorial Group Theory","author":"Stillwell J.","year":"1993","unstructured":"J. Stillwell . Classical Topology and Combinatorial Group Theory , 2 nd edition. Graduate Texts in Mathematics 72. Springer-Verlag , 1993 . J. Stillwell. Classical Topology and Combinatorial Group Theory, 2nd edition. Graduate Texts in Mathematics 72. Springer-Verlag, 1993.","edition":"2"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90115-G"},{"key":"e_1_3_2_1_49_1","volume-title":"Proc. 11th Int. Symp. Graph Drawing, 478--490","author":"C.","year":"2003","unstructured":"\u00c9. C. de Verdi\u00e8re and F. Lazarus. Optimal pants decompositions and shortest homotopic cycles on an orientable surface . Proc. 11th Int. Symp. Graph Drawing, 478--490 , 2003 . \u00c9. C. de Verdi\u00e8re and F. Lazarus. Optimal pants decompositions and shortest homotopic cycles on an orientable surface. Proc. 11th Int. Symp. Graph Drawing, 478--490, 2003."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01447877"},{"key":"e_1_3_2_1_51_1","volume-title":"Final Report on the DFG Special Joint Initiative, 233--249","author":"Welzl E.","year":"1992","unstructured":"E. Welzl . On spanning trees with low crossing numbers. Data Structures and Efficient Algorithms , Final Report on the DFG Special Joint Initiative, 233--249 , 1992 . Lecture Notes Comput. Sci. 594, Springer-Verlag . E. Welzl. On spanning trees with low crossing numbers. Data Structures and Efficient Algorithms, Final Report on the DFG Special Joint Initiative, 233--249, 1992. Lecture Notes Comput. Sci. 594, Springer-Verlag."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/990002.990007"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/1050943"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-004-1146-y"}],"event":{"name":"SoCG08: 24th Annual Symposium on Computational Geometry","sponsor":["SIGGRAPH ACM Special Interest Group on Computer Graphics and Interactive Techniques","ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"College Park MD USA","acronym":"SoCG08"},"container-title":["Proceedings of the twenty-fourth annual symposium on Computational geometry"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1377676.1377721","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1377676.1377721","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:56:39Z","timestamp":1750254999000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1377676.1377721"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6,9]]},"references-count":54,"alternative-id":["10.1145\/1377676.1377721","10.1145\/1377676"],"URL":"https:\/\/doi.org\/10.1145\/1377676.1377721","relation":{},"subject":[],"published":{"date-parts":[[2008,6,9]]},"assertion":[{"value":"2008-06-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}