--- _id: '14888' abstract: - lang: eng text: 'A face in a curve arrangement is called popular if it is bounded by the same curve multiple times. Motivated by the automatic generation of curved nonogram puzzles, we investigate possibilities to eliminate the popular faces in an arrangement by inserting a single additional curve. This turns out to be NP-hard; however, it becomes tractable when the number of popular faces is small: We present a probabilistic FPT-approach in the number of popular faces.' acknowledgement: 'This work was initiated at the 16th European Research Week on Geometric Graphs in Strobl in 2019. A.W. is supported by the Austrian Science Fund (FWF): W1230. S.T. has been funded by the Vienna Science and Technology Fund (WWTF) [10.47379/ICT19035]. A preliminary version of this work has been presented at the 38th European Workshop on Computational Geometry (EuroCG 2022) in Perugia [9]. A full version of this paper, which includes appendices but is otherwise identical, is available as a technical report [10].' alternative_title: - LNCS article_processing_charge: No author: - first_name: Phoebe full_name: De Nooijer, Phoebe last_name: De Nooijer - first_name: Soeren full_name: Terziadis, Soeren last_name: Terziadis - first_name: Alexandra full_name: Weinberger, Alexandra last_name: Weinberger - first_name: Zuzana full_name: Masárová, Zuzana id: 45CFE238-F248-11E8-B48F-1D18A9856A87 last_name: Masárová orcid: 0000-0002-6660-1322 - first_name: Tamara full_name: Mchedlidze, Tamara last_name: Mchedlidze - first_name: Maarten full_name: Löffler, Maarten last_name: Löffler - first_name: Günter full_name: Rote, Günter last_name: Rote citation: ama: 'De Nooijer P, Terziadis S, Weinberger A, et al. Removing popular faces in curve arrangements. In: 31st International Symposium on Graph Drawing and Network Visualization. Vol 14466. Springer Nature; 2024:18-33. doi:10.1007/978-3-031-49275-4_2' apa: 'De Nooijer, P., Terziadis, S., Weinberger, A., Masárová, Z., Mchedlidze, T., Löffler, M., & Rote, G. (2024). Removing popular faces in curve arrangements. In 31st International Symposium on Graph Drawing and Network Visualization (Vol. 14466, pp. 18–33). Isola delle Femmine, Palermo, Italy: Springer Nature. https://doi.org/10.1007/978-3-031-49275-4_2' chicago: De Nooijer, Phoebe, Soeren Terziadis, Alexandra Weinberger, Zuzana Masárová, Tamara Mchedlidze, Maarten Löffler, and Günter Rote. “Removing Popular Faces in Curve Arrangements.” In 31st International Symposium on Graph Drawing and Network Visualization, 14466:18–33. Springer Nature, 2024. https://doi.org/10.1007/978-3-031-49275-4_2. ieee: P. De Nooijer et al., “Removing popular faces in curve arrangements,” in 31st International Symposium on Graph Drawing and Network Visualization, Isola delle Femmine, Palermo, Italy, 2024, vol. 14466, pp. 18–33. ista: 'De Nooijer P, Terziadis S, Weinberger A, Masárová Z, Mchedlidze T, Löffler M, Rote G. 2024. Removing popular faces in curve arrangements. 31st International Symposium on Graph Drawing and Network Visualization. GD: Graph Drawing and Network Visualization, LNCS, vol. 14466, 18–33.' mla: De Nooijer, Phoebe, et al. “Removing Popular Faces in Curve Arrangements.” 31st International Symposium on Graph Drawing and Network Visualization, vol. 14466, Springer Nature, 2024, pp. 18–33, doi:10.1007/978-3-031-49275-4_2. short: P. De Nooijer, S. Terziadis, A. Weinberger, Z. Masárová, T. Mchedlidze, M. Löffler, G. Rote, in:, 31st International Symposium on Graph Drawing and Network Visualization, Springer Nature, 2024, pp. 18–33. conference: end_date: 2023-09-22 location: Isola delle Femmine, Palermo, Italy name: 'GD: Graph Drawing and Network Visualization' start_date: 2023-09-20 date_created: 2024-01-28T23:01:43Z date_published: 2024-01-06T00:00:00Z date_updated: 2024-01-29T09:45:06Z day: '06' department: - _id: UlWa - _id: HeEd doi: 10.1007/978-3-031-49275-4_2 external_id: arxiv: - '2202.12175' intvolume: ' 14466' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.2202.12175 month: '01' oa: 1 oa_version: Preprint page: 18-33 publication: 31st International Symposium on Graph Drawing and Network Visualization publication_identifier: eissn: - 1611-3349 isbn: - '9783031492747' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Removing popular faces in curve arrangements type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 14466 year: '2024' ... --- _id: '15012' abstract: - lang: eng text: We solve a problem of Dujmović and Wood (2007) by showing that a complete convex geometric graph on n vertices cannot be decomposed into fewer than n-1 star-forests, each consisting of noncrossing edges. This bound is clearly tight. We also discuss similar questions for abstract graphs. acknowledgement: János Pach’s Research partially supported by European Research Council (ERC), grant “GeoScape” No. 882971 and by the Hungarian Science Foundation (NKFIH), grant K-131529. Work by Morteza Saghafian is partially supported by the European Research Council (ERC), grant No. 788183, and by the Wittgenstein Prize, Austrian Science Fund (FWF), grant No. Z 342-N31. alternative_title: - LNCS article_processing_charge: No author: - first_name: János full_name: Pach, János id: E62E3130-B088-11EA-B919-BF823C25FEA4 last_name: Pach - first_name: Morteza full_name: Saghafian, Morteza id: f86f7148-b140-11ec-9577-95435b8df824 last_name: Saghafian - first_name: Patrick full_name: Schnider, Patrick last_name: Schnider citation: ama: 'Pach J, Saghafian M, Schnider P. Decomposition of geometric graphs into star-forests. In: 31st International Symposium on Graph Drawing and Network Visualization. Vol 14465. Springer Nature; 2024:339-346. doi:10.1007/978-3-031-49272-3_23' apa: 'Pach, J., Saghafian, M., & Schnider, P. (2024). Decomposition of geometric graphs into star-forests. In 31st International Symposium on Graph Drawing and Network Visualization (Vol. 14465, pp. 339–346). Isola delle Femmine, Palermo, Italy: Springer Nature. https://doi.org/10.1007/978-3-031-49272-3_23' chicago: Pach, János, Morteza Saghafian, and Patrick Schnider. “Decomposition of Geometric Graphs into Star-Forests.” In 31st International Symposium on Graph Drawing and Network Visualization, 14465:339–46. Springer Nature, 2024. https://doi.org/10.1007/978-3-031-49272-3_23. ieee: J. Pach, M. Saghafian, and P. Schnider, “Decomposition of geometric graphs into star-forests,” in 31st International Symposium on Graph Drawing and Network Visualization, Isola delle Femmine, Palermo, Italy, 2024, vol. 14465, pp. 339–346. ista: 'Pach J, Saghafian M, Schnider P. 2024. Decomposition of geometric graphs into star-forests. 31st International Symposium on Graph Drawing and Network Visualization. GD: Graph Drawing and Network Visualization, LNCS, vol. 14465, 339–346.' mla: Pach, János, et al. “Decomposition of Geometric Graphs into Star-Forests.” 31st International Symposium on Graph Drawing and Network Visualization, vol. 14465, Springer Nature, 2024, pp. 339–46, doi:10.1007/978-3-031-49272-3_23. short: J. Pach, M. Saghafian, P. Schnider, in:, 31st International Symposium on Graph Drawing and Network Visualization, Springer Nature, 2024, pp. 339–346. conference: end_date: 2023-09-22 location: Isola delle Femmine, Palermo, Italy name: 'GD: Graph Drawing and Network Visualization' start_date: 2023-09-20 date_created: 2024-02-18T23:01:03Z date_published: 2024-01-01T00:00:00Z date_updated: 2024-02-20T09:13:07Z day: '01' department: - _id: HeEd doi: 10.1007/978-3-031-49272-3_23 ec_funded: 1 external_id: arxiv: - '2306.13201' intvolume: ' 14465' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.2306.13201 month: '01' oa: 1 oa_version: Preprint page: 339-346 project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: The Wittgenstein Prize publication: 31st International Symposium on Graph Drawing and Network Visualization publication_identifier: eissn: - '16113349' isbn: - '9783031492716' issn: - '03029743' publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Decomposition of geometric graphs into star-forests type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 14465 year: '2024' ... --- _id: '15094' abstract: - lang: eng text: "Point sets, geometric networks, and arrangements of hyperplanes are fundamental objects in\r\ndiscrete geometry that have captivated mathematicians for centuries, if not millennia. This\r\nthesis seeks to cast new light on these structures by illustrating specific instances where a\r\ntopological perspective, specifically through discrete Morse theory and persistent homology,\r\nprovides valuable insights.\r\n\r\nAt first glance, the topology of these geometric objects might seem uneventful: point sets\r\nessentially lack of topology, arrangements of hyperplanes are a decomposition of Rd, which\r\nis a contractible space, and the topology of a network primarily involves the enumeration\r\nof connected components and cycles within the network. However, beneath this apparent\r\nsimplicity, there lies an array of intriguing structures, a small subset of which will be uncovered\r\nin this thesis.\r\n\r\nFocused on three case studies, each addressing one of the mentioned objects, this work\r\nwill showcase connections that intertwine topology with diverse fields such as combinatorial\r\ngeometry, algorithms and data structures, and emerging applications like spatial biology.\r\n\r\n" alternative_title: - ISTA Thesis article_processing_charge: No author: - first_name: Sebastiano full_name: Cultrera di Montesano, Sebastiano id: 34D2A09C-F248-11E8-B48F-1D18A9856A87 last_name: Cultrera di Montesano orcid: 0000-0001-6249-0832 citation: ama: Cultrera di Montesano S. Persistence and Morse theory for discrete geometric structures. 2024. doi:10.15479/at:ista:15094 apa: Cultrera di Montesano, S. (2024). Persistence and Morse theory for discrete geometric structures. Institute of Science and Technology Austria. https://doi.org/10.15479/at:ista:15094 chicago: Cultrera di Montesano, Sebastiano. “Persistence and Morse Theory for Discrete Geometric Structures.” Institute of Science and Technology Austria, 2024. https://doi.org/10.15479/at:ista:15094. ieee: S. Cultrera di Montesano, “Persistence and Morse theory for discrete geometric structures,” Institute of Science and Technology Austria, 2024. ista: Cultrera di Montesano S. 2024. Persistence and Morse theory for discrete geometric structures. Institute of Science and Technology Austria. mla: Cultrera di Montesano, Sebastiano. Persistence and Morse Theory for Discrete Geometric Structures. Institute of Science and Technology Austria, 2024, doi:10.15479/at:ista:15094. short: S. Cultrera di Montesano, Persistence and Morse Theory for Discrete Geometric Structures, Institute of Science and Technology Austria, 2024. date_created: 2024-03-08T15:28:10Z date_published: 2024-03-08T00:00:00Z date_updated: 2024-03-20T09:36:57Z day: '08' ddc: - '514' - '500' - '516' degree_awarded: PhD department: - _id: GradSch - _id: HeEd doi: 10.15479/at:ista:15094 ec_funded: 1 file: - access_level: open_access checksum: 1e468bfa42a7dcf04d89f4dadc621c87 content_type: application/pdf creator: scultrer date_created: 2024-03-14T08:55:07Z date_updated: 2024-03-14T08:55:07Z file_id: '15112' file_name: Thesis Sebastiano.pdf file_size: 4106872 relation: main_file success: 1 - access_level: closed checksum: bcbd213490f5a7e68855a092bbce93f1 content_type: application/zip creator: scultrer date_created: 2024-03-14T08:56:24Z date_updated: 2024-03-14T14:14:35Z file_id: '15113' file_name: Thesis (1).zip file_size: 4746234 relation: source_file file_date_updated: 2024-03-14T14:14:35Z has_accepted_license: '1' language: - iso: eng license: https://creativecommons.org/licenses/by-nc-sa/4.0/ month: '03' oa: 1 oa_version: Published Version page: '108' project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: The Wittgenstein Prize - _id: 0aa4bc98-070f-11eb-9043-e6fff9c6a316 grant_number: I4887 name: Discretization in Geometry and Dynamics - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes publication_identifier: issn: - 2663 - 337X publication_status: published publisher: Institute of Science and Technology Austria related_material: record: - id: '11660' relation: part_of_dissertation status: public - id: '11658' relation: part_of_dissertation status: public - id: '13182' relation: part_of_dissertation status: public - id: '15090' relation: part_of_dissertation status: public - id: '15091' relation: part_of_dissertation status: public - id: '15093' relation: part_of_dissertation status: public status: public supervisor: - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 title: Persistence and Morse theory for discrete geometric structures tmp: image: /images/cc_by_nc_sa.png legal_code_url: https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode name: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) short: CC BY-NC-SA (4.0) type: dissertation user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9 year: '2024' ... --- _id: '15093' abstract: - lang: eng text: We present a dynamic data structure for maintaining the persistent homology of a time series of real numbers. The data structure supports local operations, including the insertion and deletion of an item and the cutting and concatenating of lists, each in time O(log n + k), in which n counts the critical items and k the changes in the augmented persistence diagram. To achieve this, we design a tailor-made tree structure with an unconventional representation, referred to as banana tree, which may be useful in its own right. acknowledgement: The first and second authors are funded by the European Research Council under the European Union’s Horizon 2020 research and innovation programme, ERC grant no. 788183,“Alpha Shape Theory Extended (Alpha)”, by the Wittgenstein Prize, FWF grant no. Z 342-N31, and by the DFG Collaborative Research Center TRR 109, FWF grant no. I 02979-N35.The third author received funding by the European Research Council under the European Union’s Horizon 2020research and innovation programme, ERC grant no. 101019564, “The Design of Modern Fully Dynamic DataStructures (MoDynStruct)”, and by the Austrian Science Fund through the Wittgenstein Prize with FWF grant no. Z 422-N, and also by FWF grant no. I 5982-N, and by FWF grant no. P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024. The fourth author is funded by the Vienna Graduate School on Computational Optimization, FWF project no. W1260-N35. article_processing_charge: No author: - first_name: Sebastiano full_name: Cultrera di Montesano, Sebastiano id: 34D2A09C-F248-11E8-B48F-1D18A9856A87 last_name: Cultrera di Montesano orcid: 0000-0001-6249-0832 - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Lara full_name: Ost, Lara last_name: Ost citation: ama: 'Cultrera di Montesano S, Edelsbrunner H, Henzinger MH, Ost L. Dynamically maintaining the persistent homology of time series. In: Woodruff DP, ed. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics; 2024:243-295. doi:10.1137/1.9781611977912.11' apa: 'Cultrera di Montesano, S., Edelsbrunner, H., Henzinger, M. H., & Ost, L. (2024). Dynamically maintaining the persistent homology of time series. In D. P. Woodruff (Ed.), Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (pp. 243–295). Alexandria, VA, USA: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611977912.11' chicago: Cultrera di Montesano, Sebastiano, Herbert Edelsbrunner, Monika H Henzinger, and Lara Ost. “Dynamically Maintaining the Persistent Homology of Time Series.” In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), edited by David P. Woodruff, 243–95. Society for Industrial and Applied Mathematics, 2024. https://doi.org/10.1137/1.9781611977912.11. ieee: S. Cultrera di Montesano, H. Edelsbrunner, M. H. Henzinger, and L. Ost, “Dynamically maintaining the persistent homology of time series,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Alexandria, VA, USA, 2024, pp. 243–295. ista: 'Cultrera di Montesano S, Edelsbrunner H, Henzinger MH, Ost L. 2024. Dynamically maintaining the persistent homology of time series. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SODA: Symposium on Discrete Algorigthms, 243–295.' mla: Cultrera di Montesano, Sebastiano, et al. “Dynamically Maintaining the Persistent Homology of Time Series.” Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), edited by David P. Woodruff, Society for Industrial and Applied Mathematics, 2024, pp. 243–95, doi:10.1137/1.9781611977912.11. short: S. Cultrera di Montesano, H. Edelsbrunner, M.H. Henzinger, L. Ost, in:, D.P. Woodruff (Ed.), Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Society for Industrial and Applied Mathematics, 2024, pp. 243–295. conference: end_date: 2024-01-10 location: Alexandria, VA, USA name: 'SODA: Symposium on Discrete Algorigthms' start_date: 2024-01-07 date_created: 2024-03-08T10:27:39Z date_published: 2024-01-04T00:00:00Z date_updated: 2024-03-20T09:36:56Z day: '04' department: - _id: HeEd - _id: MoHe doi: 10.1137/1.9781611977912.11 ec_funded: 1 editor: - first_name: David P. full_name: Woodruff, David P. last_name: Woodruff external_id: arxiv: - '2311.01115' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/2311.01115 month: '01' oa: 1 oa_version: Preprint page: 243 - 295 project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: The Wittgenstein Prize - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' name: The design and evaluation of modern fully dynamic data structures - _id: 34def286-11ca-11ed-8bc3-da5948e1613c grant_number: Z00422 name: Wittgenstein Award - Monika Henzinger - _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe grant_number: 'P33775 ' name: Fast Algorithms for a Reactive Network Layer publication: Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) publication_identifier: eisbn: - '9781611977912' publication_status: published publisher: Society for Industrial and Applied Mathematics quality_controlled: '1' related_material: record: - id: '15094' relation: dissertation_contains status: public status: public title: Dynamically maintaining the persistent homology of time series type: conference user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9 year: '2024' ... --- _id: '15091' abstract: - lang: eng text: "Motivated by applications in the medical sciences, we study finite chromatic\r\nsets in Euclidean space from a topological perspective. Based on the persistent\r\nhomology for images, kernels and cokernels, we design provably stable\r\nhomological quantifiers that describe the geometric micro- and macro-structure\r\nof how the color classes mingle. These can be efficiently computed using\r\nchromatic variants of Delaunay and alpha complexes, and code that does these\r\ncomputations is provided." article_number: '2212.03128' article_processing_charge: No author: - first_name: Sebastiano full_name: Cultrera di Montesano, Sebastiano id: 34D2A09C-F248-11E8-B48F-1D18A9856A87 last_name: Cultrera di Montesano orcid: 0000-0001-6249-0832 - first_name: Ondrej full_name: Draganov, Ondrej id: 2B23F01E-F248-11E8-B48F-1D18A9856A87 last_name: Draganov - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Morteza full_name: Saghafian, Morteza id: f86f7148-b140-11ec-9577-95435b8df824 last_name: Saghafian citation: ama: Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. Chromatic alpha complexes. arXiv. apa: Cultrera di Montesano, S., Draganov, O., Edelsbrunner, H., & Saghafian, M. (n.d.). Chromatic alpha complexes. arXiv. chicago: Cultrera di Montesano, Sebastiano, Ondrej Draganov, Herbert Edelsbrunner, and Morteza Saghafian. “Chromatic Alpha Complexes.” ArXiv, n.d. ieee: S. Cultrera di Montesano, O. Draganov, H. Edelsbrunner, and M. Saghafian, “Chromatic alpha complexes,” arXiv. . ista: Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. Chromatic alpha complexes. arXiv, 2212.03128. mla: Cultrera di Montesano, Sebastiano, et al. “Chromatic Alpha Complexes.” ArXiv, 2212.03128. short: S. Cultrera di Montesano, O. Draganov, H. Edelsbrunner, M. Saghafian, ArXiv (n.d.). date_created: 2024-03-08T10:13:59Z date_published: 2024-02-07T00:00:00Z date_updated: 2024-03-20T09:36:56Z day: '07' department: - _id: HeEd external_id: arxiv: - '2212.03128' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/2212.03128 month: '02' oa: 1 oa_version: Preprint publication: arXiv publication_status: submitted related_material: record: - id: '15094' relation: dissertation_contains status: public status: public title: Chromatic alpha complexes tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: preprint user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9 year: '2024' ...