[{"keyword":["Triangulation of manifolds","Simplicial approximation","CW complexes","Delaunay complexes","List homomorphism problem","Topological Data Analysis"],"article_processing_charge":"Yes","supplementarymaterial":"yes","OA_place":"publisher","quality_controlled":"1","OA_type":"gold","department":[{"_id":"UlWa"}],"arxiv":1,"oa_version":"Published Version","month":"05","has_accepted_license":"1","author":[{"orcid":"0000-0002-1404-1095","id":"40ebcc9d-905f-11ef-bf0a-dc475da8a04e","full_name":"Tinarrage, Raphaël","last_name":"Tinarrage","first_name":"Raphaël"}],"scopus_import":"1","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"license":"https://creativecommons.org/licenses/by/4.0/","fulldoi":"https://doi.org/10.4230/LIPIcs.SoCG.2026.93","status":"public","date_published":"2026-05-27T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"link":[{"url":"https://doi.org/10.5281/zenodo.19251455","relation":"software"}]},"file":[{"content_type":"application/pdf","creator":"dernst","file_size":1436035,"success":1,"date_updated":"2026-06-22T07:53:13Z","checksum":"a468edad327962309688aa78678138da","relation":"main_file","access_level":"open_access","date_created":"2026-06-22T07:53:13Z","file_name":"2026_LIPIcSSoCG_Tinarrage.pdf","file_id":"22111"}],"oa":1,"date_created":"2026-06-14T22:01:43Z","ddc":["500"],"type":"conference","day":"27","publication_status":"published","file_date_updated":"2026-06-22T07:53:13Z","_id":"22000","year":"2026","language":[{"iso":"eng"}],"publication":"42nd International Symposium on Computational Geometry","title":"Simplicial approximation to CW complexes with spherical Delaunay triangulations","corr_author":"1","external_id":{"arxiv":["2112.07573"]},"volume":367,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","citation":{"ieee":"R. Tinarrage, “Simplicial approximation to CW complexes with spherical Delaunay triangulations,” in <i>42nd International Symposium on Computational Geometry</i>, New Brunswick, NJ, United States, 2026, vol. 367.","chicago":"Tinarrage, Raphaël. “Simplicial Approximation to CW Complexes with Spherical Delaunay Triangulations.” In <i>42nd International Symposium on Computational Geometry</i>, Vol. 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.93\">https://doi.org/10.4230/LIPIcs.SoCG.2026.93</a>.","ista":"Tinarrage R. 2026. Simplicial approximation to CW complexes with spherical Delaunay triangulations. 42nd International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry vol. 367, 93:1-93:22.","ama":"Tinarrage R. Simplicial approximation to CW complexes with spherical Delaunay triangulations. In: <i>42nd International Symposium on Computational Geometry</i>. Vol 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.93\">10.4230/LIPIcs.SoCG.2026.93</a>","short":"R. Tinarrage, in:, 42nd International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.","apa":"Tinarrage, R. (2026). Simplicial approximation to CW complexes with spherical Delaunay triangulations. In <i>42nd International Symposium on Computational Geometry</i> (Vol. 367). New Brunswick, NJ, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.93\">https://doi.org/10.4230/LIPIcs.SoCG.2026.93</a>","mla":"Tinarrage, Raphaël. “Simplicial Approximation to CW Complexes with Spherical Delaunay Triangulations.” <i>42nd International Symposium on Computational Geometry</i>, vol. 367, 93:1-93:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.93\">10.4230/LIPIcs.SoCG.2026.93</a>."},"intvolume":"       367","researchdata_availability":"no","doi":"10.4230/LIPIcs.SoCG.2026.93","conference":{"name":"SoCG: Symposium on Computational Geometry","location":"New Brunswick, NJ, United States","start_date":"2026-06-02","end_date":"2026-06-05"},"date_updated":"2026-06-22T11:28:26Z","article_number":"93:1-93:22","publication_identifier":{"isbn":["9783959774185"],"eissn":["1868-8969"]},"das_tickbox":"0","abstract":[{"lang":"eng","text":"Simplicial approximation provides a framework for constructing simplicial complexes that are homotopy equivalent to a given manifold, provided a CW structure is explicitly known. However, its conventional implementation quickly becomes intractable on a computer: barycentric subdivision produces poorly shaped simplices, and the star condition introduces many vertices. To address these limitations, this article develops a subdivision scheme based on spherical Delaunay triangulations, which attains better refinement properties than barycentric subdivisions. Moreover, the star condition is reframed as two independent problems, one geometric and the other combinatorial, respectively tackled in the language of locally equiconnected spaces and the list homomorphism problem, allowing an exponential reduction in the number of vertices. Via a prototype implementation, we obtain simplicial complexes homotopy equivalent to Grassmannians and Stiefel manifolds up to dimension 5."}]},{"acknowledgement":"Jakub Leśkiewicz wants to thank his supervisor, Prof. Marian Mrozek, forscientific guidance, patience, and opportunity to delay the rest of his duties while writing this work.\r\nThe author also extends thanks to his entire family, to Zuzanna Świątek, and to Mikołaj Kardyś,\r\nBEng, MSc, for providing meals during the most intensive periods of work. Jakub Leśkiewicz: The research was partially funded by the Polish National Science Center under Opus Grant No. 2019/35/B/ST1/00874 and Opus Grant 2025/57/B/ST1/00550. Bartosz Furmanek: The research was partially funded by the Polish National Science Center under Opus Grant No. 2019/35/B/ST1/00874 and Opus Grant 2025/57/B/ST1/00550. Michał Lipiński: This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 101034413. \r\nDmitriy Morozov: This work was supported in part by the U.S. Department of Energy, Office\r\nof Science, Office of Advanced Scientific Computing Research, under Contract No. DE-AC02-\r\n05CH11231.","author":[{"first_name":"Jakub","last_name":"Leśkiewicz","full_name":"Leśkiewicz, Jakub"},{"last_name":"Furmanek","full_name":"Furmanek, Bartosz","first_name":"Bartosz"},{"full_name":"Lipiński, Michał","last_name":"Lipiński","first_name":"Michał","orcid":"0000-0001-9789-9750","id":"dfffb474-4317-11ee-8f5c-fe3fc95a425e"},{"first_name":"Dmitriy","last_name":"Morozov","full_name":"Morozov, Dmitriy"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"scopus_import":"1","project":[{"name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020","grant_number":"101034413","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2026-05-27T00:00:00Z","status":"public","fulldoi":"https://doi.org/10.4230/LIPIcs.SoCG.2026.72","date_created":"2026-06-14T22:01:43Z","oa":1,"file":[{"relation":"main_file","checksum":"3be91c06fdf716c8735b6af64a09a921","date_created":"2026-06-22T07:39:21Z","access_level":"open_access","file_id":"22110","file_name":"2026_LIPIcSSoCG_Leskiewicz.pdf","content_type":"application/pdf","creator":"dernst","file_size":2052749,"date_updated":"2026-06-22T07:39:21Z","success":1}],"article_processing_charge":"No","keyword":["persistent homology","topological simplification","depth posets"],"OA_type":"gold","quality_controlled":"1","OA_place":"publisher","arxiv":1,"oa_version":"Published Version","department":[{"_id":"HeEd"}],"month":"05","has_accepted_license":"1","citation":{"apa":"Leśkiewicz, J., Furmanek, B., Lipiński, M., &#38; Morozov, D. (2026). Topological simplification guided by forbidden regions. In <i>42nd International Symposium on Computational Geometry</i> (Vol. 367). New Brunswick, NJ, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.72\">https://doi.org/10.4230/LIPIcs.SoCG.2026.72</a>","mla":"Leśkiewicz, Jakub, et al. “Topological Simplification Guided by Forbidden Regions.” <i>42nd International Symposium on Computational Geometry</i>, vol. 367, 72:1-72:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.72\">10.4230/LIPIcs.SoCG.2026.72</a>.","ieee":"J. Leśkiewicz, B. Furmanek, M. Lipiński, and D. Morozov, “Topological simplification guided by forbidden regions,” in <i>42nd International Symposium on Computational Geometry</i>, New Brunswick, NJ, United States, 2026, vol. 367.","chicago":"Leśkiewicz, Jakub, Bartosz Furmanek, Michał Lipiński, and Dmitriy Morozov. “Topological Simplification Guided by Forbidden Regions.” In <i>42nd International Symposium on Computational Geometry</i>, Vol. 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.72\">https://doi.org/10.4230/LIPIcs.SoCG.2026.72</a>.","ista":"Leśkiewicz J, Furmanek B, Lipiński M, Morozov D. 2026. Topological simplification guided by forbidden regions. 42nd International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 367, 72:1-72:17.","short":"J. Leśkiewicz, B. Furmanek, M. Lipiński, D. Morozov, in:, 42nd International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.","ama":"Leśkiewicz J, Furmanek B, Lipiński M, Morozov D. Topological simplification guided by forbidden regions. In: <i>42nd International Symposium on Computational Geometry</i>. Vol 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.72\">10.4230/LIPIcs.SoCG.2026.72</a>"},"intvolume":"       367","date_updated":"2026-06-22T07:45:36Z","conference":{"location":"New Brunswick, NJ, United States","name":"SoCG: Symposium on Computational Geometry","end_date":"2026-06-05","start_date":"2026-06-02"},"doi":"10.4230/LIPIcs.SoCG.2026.72","das_tickbox":"0","article_number":"72:1-72:17","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959774185"]},"abstract":[{"text":"Topological simplification is the process of reducing complexity of a function while maintaining its essential features. Its goal is to find a new filter function, which reorders cells of the input complex in a way which eliminates some persistent homological features, without affecting the rest. We present a new approach to simplification based on the concept of forbidden regions and combinatorial dynamics. It allows us to reorder and cancel critical values, whose cancellation is not possible using existing methods because they are not consecutive in the total order. Each such cancellation takes O(c⋅n) time in the worst case, where c is the number of birth-death pairs and n is the size of the input complex.","lang":"eng"}],"type":"conference","ddc":["500"],"publication_status":"published","day":"27","publication":"42nd International Symposium on Computational Geometry","corr_author":"1","title":"Topological simplification guided by forbidden regions","_id":"22002","year":"2026","file_date_updated":"2026-06-22T07:39:21Z","language":[{"iso":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","alternative_title":["LIPIcs"],"external_id":{"arxiv":["2603.16416"]},"ec_funded":1,"volume":367},{"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"project":[{"call_identifier":"FWF","name":"Algebraic Footprints of Geometric Features in Homology","grant_number":"I04245","_id":"26AD5D90-B435-11E9-9278-68D0E5697425"}],"scopus_import":"1","author":[{"full_name":"Adams, Henry","last_name":"Adams","first_name":"Henry"},{"first_name":"Sushovan","last_name":"Majhi","full_name":"Majhi, Sushovan"},{"full_name":"Manin, Fedor","last_name":"Manin","first_name":"Fedor"},{"first_name":"Ziga","full_name":"Virk, Ziga","last_name":"Virk","id":"2E36B656-F248-11E8-B48F-1D18A9856A87"},{"id":"c8b3499c-7a77-11eb-b046-aa368cbbf2ad","orcid":"0000-0001-8686-1888","first_name":"Nicolò","last_name":"Zava","full_name":"Zava, Nicolò"}],"acknowledgement":"Funding Henry Adams: Simons Foundation Travel Support for Mathematicians.\r\nŽiga Virk: Slovene research agency grant P1-0292.\r\nNicolò Zava: FWF Grant, Project number I4245-N35.\r\n","fulldoi":"https://doi.org/10.4230/LIPIcs.SoCG.2026.3","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2026-05-27T00:00:00Z","file":[{"access_level":"open_access","date_created":"2026-06-22T08:43:47Z","checksum":"25d27c016409563196b8aecfe5bfdf41","relation":"main_file","file_name":"2026_LIPIcSSoCG_Adams.pdf","file_id":"22115","creator":"dernst","content_type":"application/pdf","success":1,"date_updated":"2026-06-22T08:43:47Z","file_size":1091310}],"oa":1,"date_created":"2026-06-14T22:01:44Z","keyword":["Gromov–Hausdorff distance","distortion","connectedness","Borsuk–Ulam theorem"],"article_processing_charge":"Yes","arxiv":1,"oa_version":"Published Version","department":[{"_id":"HeEd"}],"OA_type":"gold","quality_controlled":"1","OA_place":"publisher","month":"05","has_accepted_license":"1","intvolume":"       367","citation":{"apa":"Adams, H., Majhi, S., Manin, F., Virk, Z., &#38; Zava, N. (2026). Lower bounding the Gromov–Hausdorff distance in metric graphs. In <i>42nd International Symposium on Computational Geometry</i> (Vol. 367). New Brunswick, NJ, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.3\">https://doi.org/10.4230/LIPIcs.SoCG.2026.3</a>","mla":"Adams, Henry, et al. “Lower Bounding the Gromov–Hausdorff Distance in Metric Graphs.” <i>42nd International Symposium on Computational Geometry</i>, vol. 367, 3:1-3:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.3\">10.4230/LIPIcs.SoCG.2026.3</a>.","ista":"Adams H, Majhi S, Manin F, Virk Z, Zava N. 2026. Lower bounding the Gromov–Hausdorff distance in metric graphs. 42nd International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 367, 3:1-3:16.","chicago":"Adams, Henry, Sushovan Majhi, Fedor Manin, Ziga Virk, and Nicolò Zava. “Lower Bounding the Gromov–Hausdorff Distance in Metric Graphs.” In <i>42nd International Symposium on Computational Geometry</i>, Vol. 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.3\">https://doi.org/10.4230/LIPIcs.SoCG.2026.3</a>.","ieee":"H. Adams, S. Majhi, F. Manin, Z. Virk, and N. Zava, “Lower bounding the Gromov–Hausdorff distance in metric graphs,” in <i>42nd International Symposium on Computational Geometry</i>, New Brunswick, NJ, United States, 2026, vol. 367.","short":"H. Adams, S. Majhi, F. Manin, Z. Virk, N. Zava, in:, 42nd International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.","ama":"Adams H, Majhi S, Manin F, Virk Z, Zava N. Lower bounding the Gromov–Hausdorff distance in metric graphs. In: <i>42nd International Symposium on Computational Geometry</i>. Vol 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.3\">10.4230/LIPIcs.SoCG.2026.3</a>"},"doi":"10.4230/LIPIcs.SoCG.2026.3","conference":{"location":"New Brunswick, NJ, United States","name":"SoCG: Symposium on Computational Geometry","end_date":"2026-06-05","start_date":"2026-06-02"},"date_updated":"2026-06-22T08:49:17Z","publication_identifier":{"isbn":["9783959774185"],"eissn":["1868-8969"]},"article_number":"3:1-3:16","das_tickbox":"0","abstract":[{"lang":"eng","text":"Let G be a finite, connected metric graph and let X be a subset of G. If X is sufficiently dense in G, we show that the Gromov-Hausdorff distance matches the Hausdorff distance, namely d_GH(G,X) = d_H(G,X). When the metric graph is the circle G = S¹ with circumference 2π, a recent study established the equality d_GH(S¹,X) = d_H(S¹,X) whenever d_GH(S¹,X) < π/6. Our results relax this hypothesis to d_GH(S¹,X) < π/3, and furthermore, we show that the constant π/3 is the best possible. We lower bound the Gromov-Hausdorff distance d_GH(G,X) by the Hausdorff distance d_H(G,X) via a simple topological obstruction: the existence of a possibly discontinuous function f: G → X with too small distortion contradicts the connectedness of G."}],"ddc":["500"],"type":"conference","day":"27","publication_status":"published","language":[{"iso":"eng"}],"_id":"22003","file_date_updated":"2026-06-22T08:43:47Z","year":"2026","title":"Lower bounding the Gromov–Hausdorff distance in metric graphs","corr_author":"1","publication":"42nd International Symposium on Computational Geometry","volume":367,"external_id":{"arxiv":["2411.09182"]},"alternative_title":["LIPIcs"],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik"},{"abstract":[{"lang":"eng","text":"Recent research on computing the diameter of geometric intersection graphs has made significant strides, primarily focusing on the 2D case [Duraj et al., 2024; Hsien-Chih Chang et al., 2024; Chan et al., 2025] where truly subquadratic-time algorithms were given for simple objects such as unit-disks and (axis-aligned) squares. However, in three or higher dimensions, there is no known truly subquadratic-time algorithm for any intersection graph of non-trivial objects, even basic ones such as unit balls or (axis-aligned) unit cubes. This was partially explained by the pioneering work of Bringmann et al. [Karl Bringmann et al., 2022] which gave several truly subquadratic lower bounds, notably for unit balls or unit cubes in 3D when the graph diameter Δ is at least Ω(log n), hinting at a pessimistic outlook for the complexity of the diameter problem in higher dimensions. In this paper, we substantially extend the landscape of diameter computation for objects in three and higher dimensions, giving a few positive results. Our highlighted findings include:  \r\n1) A truly subquadratic-time algorithm for deciding if the diameter of unit cubes in 3D is at most 3 (Diameter-3 hereafter), the first algorithm of its kind for objects in 3D or higher dimensions. Our algorithm is based on a novel connection to pseudolines, which is of independent interest. \r\n2) A truly subquadratic time lower bound for Diameter-3 of unit balls in 3D under the Orthogonal Vector (OV) hypothesis, giving the first separation between unit balls and unit cubes in the small diameter regime. Previously, computing the diameter for both objects was known to be quadratic hard when the diameter is Ω(log n) [Karl Bringmann et al., 2022]. \r\n3) A near-linear-time algorithm for Diameter-2 of unit cubes in 3D, generalizing the previous result for unit squares in 2D [Karl Bringmann et al., 2022]. \r\n4) A truly subquadratic-time algorithm and lower bound for Diameter-2 and Diameter-3 of rectangular boxes (of arbitrary dimension and sizes), respectively."}],"das_tickbox":"0","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959774185"]},"article_number":"29:1-29:15","date_updated":"2026-06-22T08:37:44Z","doi":"10.4230/LIPIcs.SoCG.2026.29","conference":{"location":"New Brunswick, NJ, United States","name":"SoCG: Symposium on Computational Geometry","end_date":"2026-06-05","start_date":"2026-06-02"},"intvolume":"       367","citation":{"mla":"Chan, Timothy M., et al. “Charting the Diameter Computation Landscape of Intersection Graphs in 3D and Above.” <i>42nd International Symposium on Computational Geometry</i>, vol. 367, 29:1-29:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.29\">10.4230/LIPIcs.SoCG.2026.29</a>.","apa":"Chan, T. M., Chang, H. C., Gao, J., Kisfaludi-Bak, S., Le, H., &#38; Zheng, D. W. (2026). Charting the diameter computation landscape of intersection graphs in 3D and above. In <i>42nd International Symposium on Computational Geometry</i> (Vol. 367). New Brunswick, NJ, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.29\">https://doi.org/10.4230/LIPIcs.SoCG.2026.29</a>","ama":"Chan TM, Chang HC, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. Charting the diameter computation landscape of intersection graphs in 3D and above. In: <i>42nd International Symposium on Computational Geometry</i>. Vol 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.29\">10.4230/LIPIcs.SoCG.2026.29</a>","short":"T.M. Chan, H.C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, D.W. Zheng, in:, 42nd International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.","ista":"Chan TM, Chang HC, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. 2026. Charting the diameter computation landscape of intersection graphs in 3D and above. 42nd International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 367, 29:1-29:15.","chicago":"Chan, Timothy M., Hsien Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, and Da Wei Zheng. “Charting the Diameter Computation Landscape of Intersection Graphs in 3D and Above.” In <i>42nd International Symposium on Computational Geometry</i>, Vol. 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.29\">https://doi.org/10.4230/LIPIcs.SoCG.2026.29</a>.","ieee":"T. M. Chan, H. C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, and D. W. Zheng, “Charting the diameter computation landscape of intersection graphs in 3D and above,” in <i>42nd International Symposium on Computational Geometry</i>, New Brunswick, NJ, United States, 2026, vol. 367."},"alternative_title":["LIPIcs"],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","volume":367,"external_id":{"arxiv":["2603.21790"]},"corr_author":"1","title":"Charting the diameter computation landscape of intersection graphs in 3D and above","publication":"42nd International Symposium on Computational Geometry","language":[{"iso":"eng"}],"_id":"22004","year":"2026","file_date_updated":"2026-06-22T08:34:11Z","publication_status":"published","day":"27","type":"conference","ddc":["000"],"date_created":"2026-06-14T22:01:44Z","file":[{"creator":"dernst","content_type":"application/pdf","success":1,"date_updated":"2026-06-22T08:34:11Z","file_size":918197,"access_level":"open_access","date_created":"2026-06-22T08:34:11Z","checksum":"ffff03934cc182757d6db82d88f896e6","relation":"main_file","file_name":"2026_LIPIcSSoCG_Chan.pdf","file_id":"22114"}],"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2026-05-27T00:00:00Z","fulldoi":"https://doi.org/10.4230/LIPIcs.SoCG.2026.29","status":"public","acknowledgement":"Timothy M. Chan: Supported by NSF grant CCF-2224271.\r\nHsien-Chih Chang: Supported by NSF CAREER award CCF-2443017.\r\nJie Gao: Supported by NSF DMS-2220271, DMS-2311064, IIS-2229876, CCF-2118953, CNS-2515159.\r\nSándor Kisfaludi-Bak: Supported by the Research Council of Finland, Grant 363444.\r\nHung Le: Supported by an NSF grant CCF-2517033 and an NSF CAREER Award CCF-2237288. Da Wei Zheng: This project has received funding from the Austrian Science Fund (FWF) grant\r\nDOI 10.55776/I5982. For open access purposes, the author has applied a CC BY public copyright license to any author-accepted manuscript version arising from this submission.","project":[{"name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"scopus_import":"1","author":[{"first_name":"Timothy M.","full_name":"Chan, Timothy M.","last_name":"Chan"},{"last_name":"Chang","full_name":"Chang, Hsien Chih","first_name":"Hsien Chih"},{"last_name":"Gao","full_name":"Gao, Jie","first_name":"Jie"},{"first_name":"Sándor","full_name":"Kisfaludi-Bak, Sándor","last_name":"Kisfaludi-Bak"},{"first_name":"Hung","last_name":"Le","full_name":"Le, Hung"},{"first_name":"Da Wei","last_name":"Zheng","full_name":"Zheng, Da Wei","id":"af77956b-e859-11ef-8dc9-d301b898e32f"}],"has_accepted_license":"1","month":"05","department":[{"_id":"MoHe"}],"oa_version":"Published Version","arxiv":1,"OA_place":"publisher","OA_type":"gold","quality_controlled":"1","keyword":["Graph Diameter","Geometric Intersection Graphs","Unit Ball Graphs"],"article_processing_charge":"Yes"},{"date_created":"2026-07-13T09:56:38Z","oa":1,"file":[{"access_level":"open_access","date_created":"2026-07-14T06:08:05Z","checksum":"9dfb96ee66985c724b499b0e5888dc8e","relation":"main_file","file_name":"2026_LIPIcSSoCG_Edelsbrunner.pdf","file_id":"22329","creator":"dernst","content_type":"application/pdf","success":1,"date_updated":"2026-07-14T06:08:05Z","file_size":2902144}],"date_published":"2026-05-27T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","fulldoi":"https://doi.org/10.4230/LIPICS.SOCG.2026.41","status":"public","acknowledgement":"The authors thank Jakub Leśkiewicz and Bartosz Furmanek for discussions\r\nthat helped improve the paper. Herbert Edelsbrunner: DFG Collaborative Research Center TRR 109, Austrian Science\r\nFund (FWF), grant no. I 02979-N35\r\nMichał Lipiński: European Union’s Horizon 2020 research and innovation programme under the\r\nMarie Skłodowska-Curie Grant Agreement No. 101034413\r\nMarian Mrozek: Polish National Science Center under Opus Grant 2019/35/B/ST1/00874 and Opus\r\nGrant 2025/57/B/ST1/00550","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"project":[{"name":"Persistence and stability of geometric complexes","call_identifier":"FWF","grant_number":"I02979-N35","_id":"2561EBF4-B435-11E9-9278-68D0E5697425"},{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program"}],"scopus_import":"1","author":[{"first_name":"Herbert","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833"},{"first_name":"Michał","last_name":"Lipiński","full_name":"Lipiński, Michał","id":"dfffb474-4317-11ee-8f5c-fe3fc95a425e","orcid":"0000-0001-9789-9750"},{"orcid":"0000-0002-0619-6417","last_name":"Mrozek","full_name":"Mrozek, Marian","first_name":"Marian"},{"orcid":"0000-0003-2449-1433","id":"15ebd7cf-15bf-11ee-aebd-bb4bb5121ea8","last_name":"Soriano Trigueros","full_name":"Soriano Trigueros, Manuel","first_name":"Manuel"},{"id":"afd27eda-91c1-11f0-aad8-c6edbec24c04","first_name":"Fedor","full_name":"Zimin, Fedor","last_name":"Zimin"}],"has_accepted_license":"1","month":"05","oa_version":"Published Version","department":[{"_id":"HeEd"},{"_id":"GradSch"}],"arxiv":1,"quality_controlled":"1","OA_type":"gold","OA_place":"publisher","supplementarymaterial":"no","article_processing_charge":"Yes","keyword":["Algebraic topology","Lefschetz complexes","persistent homology","vines and vineyards","birth-death pairs","shallow pairs","relations","partial orders","transpositions","Theory of computation → Computational geometry"],"abstract":[{"lang":"eng","text":"The depth poset of a filtered Lefschetz complex reflects the dependencies between the cancellations of different shallow birth-death pairs. Using the fast algorithms for computing the depth poset in [Edelsbrunner et al., 2026] and for updating the persistence diagram under transpositions in [Cohen-Steiner et al., 2006], we give a complete case analysis of how transpositions of cells in the filter affect the depth poset. In addition, we present statistics on the depth poset for random point data and its sensitivity to the transpositions that occur in random straight-line homotopies."}],"das_tickbox":"0","publication_identifier":{"isbn":["9783959774185"],"eissn":["1868-8969"]},"article_number":"41:1-41:18","date_updated":"2026-08-12T09:02:56Z","researchdata_availability":"no","conference":{"name":"SoCG: Symposium on Computational Geometry","location":"New Brunswick, NJ, United States","start_date":"2026-06-02","end_date":"2026-06-05"},"doi":"10.4230/LIPICS.SOCG.2026.41","intvolume":"       367","citation":{"ista":"Edelsbrunner H, Lipiński M, Mrozek M, Soriano Trigueros M, Zimin F. 2026. The depth poset under transpositions in the filter. 42nd International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 367, 41:1-41:18.","chicago":"Edelsbrunner, Herbert, Michał Lipiński, Marian Mrozek, Manuel Soriano Trigueros, and Fedor Zimin. “The Depth Poset under Transpositions in the Filter.” In <i>42nd International Symposium on Computational Geometry</i>, Vol. 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPICS.SOCG.2026.41\">https://doi.org/10.4230/LIPICS.SOCG.2026.41</a>.","ieee":"H. Edelsbrunner, M. Lipiński, M. Mrozek, M. Soriano Trigueros, and F. Zimin, “The depth poset under transpositions in the filter,” in <i>42nd International Symposium on Computational Geometry</i>, New Brunswick, NJ, United States, 2026, vol. 367.","ama":"Edelsbrunner H, Lipiński M, Mrozek M, Soriano Trigueros M, Zimin F. The depth poset under transpositions in the filter. In: <i>42nd International Symposium on Computational Geometry</i>. Vol 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPICS.SOCG.2026.41\">10.4230/LIPICS.SOCG.2026.41</a>","short":"H. Edelsbrunner, M. Lipiński, M. Mrozek, M. Soriano Trigueros, F. Zimin, in:, 42nd International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.","apa":"Edelsbrunner, H., Lipiński, M., Mrozek, M., Soriano Trigueros, M., &#38; Zimin, F. (2026). The depth poset under transpositions in the filter. In <i>42nd International Symposium on Computational Geometry</i> (Vol. 367). New Brunswick, NJ, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.SOCG.2026.41\">https://doi.org/10.4230/LIPICS.SOCG.2026.41</a>","mla":"Edelsbrunner, Herbert, et al. “The Depth Poset under Transpositions in the Filter.” <i>42nd International Symposium on Computational Geometry</i>, vol. 367, 41:1-41:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPICS.SOCG.2026.41\">10.4230/LIPICS.SOCG.2026.41</a>."},"alternative_title":["LIPIcs"],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","volume":367,"ec_funded":1,"external_id":{"arxiv":["2511.21961"]},"title":"The depth poset under transpositions in the filter","corr_author":"1","publication":"42nd International Symposium on Computational Geometry","language":[{"iso":"eng"}],"_id":"22299","file_date_updated":"2026-07-14T06:08:05Z","year":"2026","publication_status":"published","day":"27","type":"conference","ddc":["500"]}]