[{"type":"journal_article","file":[{"success":1,"file_name":"2024_JourGraphAlgorithms_deNooijer.pdf","content_type":"application/pdf","date_created":"2024-12-03T09:45:00Z","creator":"dernst","access_level":"open_access","date_updated":"2024-12-03T09:45:00Z","relation":"main_file","file_id":"18609","checksum":"be611da6f9d790dc980d6fb7283fe889","file_size":1582493}],"oa":1,"date_created":"2024-12-01T23:01:54Z","abstract":[{"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 randomized FPT-time algorithm where the parameter is the number of popular faces.","lang":"eng"}],"status":"public","quality_controlled":"1","arxiv":1,"corr_author":"1","article_type":"original","DOAJ_listed":"1","day":"03","scopus_import":"1","page":"47-82","author":[{"full_name":"De Nooijer, Phoebe","last_name":"De Nooijer","first_name":"Phoebe"},{"first_name":"Soeren","last_name":"Terziadis","full_name":"Terziadis, Soeren"},{"full_name":"Weinberger, Alexandra","first_name":"Alexandra","last_name":"Weinberger"},{"id":"45CFE238-F248-11E8-B48F-1D18A9856A87","full_name":"Masárová, Zuzana","first_name":"Zuzana","last_name":"Masárová","orcid":"0000-0002-6660-1322"},{"full_name":"Mchedlidze, Tamara","first_name":"Tamara","last_name":"Mchedlidze"},{"last_name":"Löffler","first_name":"Maarten","full_name":"Löffler, Maarten"},{"first_name":"Günter","last_name":"Rote","full_name":"Rote, Günter"}],"year":"2024","doi":"10.7155/jgaa.v28i2.2988","title":"Removing popular faces in curve arrangements","month":"11","ddc":["510"],"tmp":{"short":"CC BY (4.0)","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"},"acknowledgement":"This work was initiated at the 16th European Research Week on Geometric Graphs in Strobl in 2019. A.W. has been supported by the Austrian Science Fund (FWF): W1230. S.T. has been funded by the Vienna Science and Technology Fund (WWTF) [10.47379/ICT19035] and by the NWO Gravitation project NETWORKS under grant no. 024.002.003. Part of the work was done while A.W. was emplyed at Graz University of Technology. Preliminary versions of this work have been presented at the 38th European Workshop on Computational Geometry (EuroCG\r\n2022) in Perugia [10] and at the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023) in Isola delle Femmine [11].","intvolume":"        28","file_date_updated":"2024-12-03T09:45:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"Journal of Graph Algorithms and Applications","license":"https://creativecommons.org/licenses/by/4.0/","date_published":"2024-11-03T00:00:00Z","volume":28,"oa_version":"Published Version","publication_status":"published","publisher":"Brown University","language":[{"iso":"eng"}],"OA_type":"gold","OA_place":"publisher","has_accepted_license":"1","publication_identifier":{"issn":["1526-1719"]},"citation":{"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.” <i>Journal of Graph Algorithms and Applications</i>. Brown University, 2024. <a href=\"https://doi.org/10.7155/jgaa.v28i2.2988\">https://doi.org/10.7155/jgaa.v28i2.2988</a>.","ieee":"P. De Nooijer <i>et al.</i>, “Removing popular faces in curve arrangements,” <i>Journal of Graph Algorithms and Applications</i>, vol. 28, no. 2. Brown University, pp. 47–82, 2024.","apa":"De Nooijer, P., Terziadis, S., Weinberger, A., Masárová, Z., Mchedlidze, T., Löffler, M., &#38; Rote, G. (2024). Removing popular faces in curve arrangements. <i>Journal of Graph Algorithms and Applications</i>. Brown University. <a href=\"https://doi.org/10.7155/jgaa.v28i2.2988\">https://doi.org/10.7155/jgaa.v28i2.2988</a>","mla":"De Nooijer, Phoebe, et al. “Removing Popular Faces in Curve Arrangements.” <i>Journal of Graph Algorithms and Applications</i>, vol. 28, no. 2, Brown University, 2024, pp. 47–82, doi:<a href=\"https://doi.org/10.7155/jgaa.v28i2.2988\">10.7155/jgaa.v28i2.2988</a>.","ama":"De Nooijer P, Terziadis S, Weinberger A, et al. Removing popular faces in curve arrangements. <i>Journal of Graph Algorithms and Applications</i>. 2024;28(2):47-82. doi:<a href=\"https://doi.org/10.7155/jgaa.v28i2.2988\">10.7155/jgaa.v28i2.2988</a>","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. Journal of Graph Algorithms and Applications. 28(2), 47–82.","short":"P. De Nooijer, S. Terziadis, A. Weinberger, Z. Masárová, T. Mchedlidze, M. Löffler, G. Rote, Journal of Graph Algorithms and Applications 28 (2024) 47–82."},"department":[{"_id":"UlWa"},{"_id":"HeEd"}],"external_id":{"arxiv":["2202.12175"]},"_id":"18604","date_updated":"2024-12-03T09:49:18Z","article_processing_charge":"No","issue":"2"},{"intvolume":"        27","file_date_updated":"2023-08-07T08:00:48Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"Journal of Graph Algorithms and Applications","tmp":{"short":"CC BY (4.0)","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"},"acknowledgement":"This work was initiated during the Workshop on Geometric Graphs in November 2019 in Strobl, Austria. We would like to thank Oswin Aichholzer, Fabian Klute, Man-Kwun Chiu, Martin Balko, Pavel Valtr for their avid discussions during the workshop. The first author has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 754411. The second author has been supported by the German Research Foundation DFG Project FE 340/12-1. An extended abstract of this paper has been published in the proceedings of WALCOM 2022 in the Springer LNCS series, vol. 13174, pages 383–395.","publication_status":"published","publisher":"Brown University","volume":27,"date_published":"2023-07-01T00:00:00Z","ec_funded":1,"oa_version":"Published Version","publication_identifier":{"issn":["1526-1719"]},"citation":{"apa":"Arroyo Guevara, A. M., &#38; Felsner, S. (2023). Approximating the bundled crossing number. <i>Journal of Graph Algorithms and Applications</i>. Brown University. <a href=\"https://doi.org/10.7155/jgaa.00629\">https://doi.org/10.7155/jgaa.00629</a>","short":"A.M. Arroyo Guevara, S. Felsner, Journal of Graph Algorithms and Applications 27 (2023) 433–457.","ista":"Arroyo Guevara AM, Felsner S. 2023. Approximating the bundled crossing number. Journal of Graph Algorithms and Applications. 27(6), 433–457.","ama":"Arroyo Guevara AM, Felsner S. Approximating the bundled crossing number. <i>Journal of Graph Algorithms and Applications</i>. 2023;27(6):433-457. doi:<a href=\"https://doi.org/10.7155/jgaa.00629\">10.7155/jgaa.00629</a>","mla":"Arroyo Guevara, Alan M., and Stefan Felsner. “Approximating the Bundled Crossing Number.” <i>Journal of Graph Algorithms and Applications</i>, vol. 27, no. 6, Brown University, 2023, pp. 433–57, doi:<a href=\"https://doi.org/10.7155/jgaa.00629\">10.7155/jgaa.00629</a>.","ieee":"A. M. Arroyo Guevara and S. Felsner, “Approximating the bundled crossing number,” <i>Journal of Graph Algorithms and Applications</i>, vol. 27, no. 6. Brown University, pp. 433–457, 2023.","chicago":"Arroyo Guevara, Alan M, and Stefan Felsner. “Approximating the Bundled Crossing Number.” <i>Journal of Graph Algorithms and Applications</i>. Brown University, 2023. <a href=\"https://doi.org/10.7155/jgaa.00629\">https://doi.org/10.7155/jgaa.00629</a>."},"department":[{"_id":"UlWa"}],"external_id":{"arxiv":["2109.14892"]},"language":[{"iso":"eng"}],"has_accepted_license":"1","issue":"6","_id":"13969","date_updated":"2025-09-10T09:35:55Z","article_processing_charge":"Yes","date_created":"2023-08-06T22:01:11Z","abstract":[{"lang":"eng","text":"Bundling crossings is a strategy which can enhance the readability\r\nof graph drawings. In this paper we consider good drawings, i.e., we require that\r\nany two edges have at most one common point which can be a common vertex or a\r\ncrossing. Our main result is that there is a polynomial-time algorithm to compute an\r\n8-approximation of the bundled crossing number of a good drawing with no toothed\r\nhole. In general the number of toothed holes has to be added to the 8-approximation.\r\nIn the special case of circular drawings the approximation factor is 8, this improves\r\nupon the 10-approximation of Fink et al. [14]. Our approach also works with the same\r\napproximation factor for families of pseudosegments, i.e., curves intersecting at most\r\nonce. We also show how to compute a 9/2-approximation when the intersection graph of\r\nthe pseudosegments is bipartite and has no toothed hole."}],"type":"journal_article","oa":1,"file":[{"success":1,"date_created":"2023-08-07T08:00:48Z","content_type":"application/pdf","file_name":"2023_JourGraphAlgorithms_Arroyo.pdf","date_updated":"2023-08-07T08:00:48Z","creator":"dernst","access_level":"open_access","relation":"main_file","file_id":"13979","file_size":865774,"checksum":"9c30d2b8e324cc1c904f2aeec92013a3"}],"corr_author":"1","status":"public","arxiv":1,"quality_controlled":"1","day":"01","page":"433-457","scopus_import":"1","author":[{"full_name":"Arroyo Guevara, Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","last_name":"Arroyo Guevara","first_name":"Alan M","orcid":"0000-0003-2401-8670"},{"full_name":"Felsner, Stefan","first_name":"Stefan","last_name":"Felsner"}],"project":[{"name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","call_identifier":"H2020"}],"year":"2023","doi":"10.7155/jgaa.00629","article_type":"original","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"11185"}]},"ddc":["510"],"title":"Approximating the bundled crossing number","month":"07"},{"file_date_updated":"2022-08-22T06:42:42Z","intvolume":"        26","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"Journal of Graph Algorithms and Applications","tmp":{"short":"CC BY (4.0)","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"},"acknowledgement":"A.A. funded by the Marie Sklodowska-Curie grant agreement No 754411. Z.M. partially funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31. I.P., D.P., and B.V. partially supported by FWF within the collaborative DACH project Arrangements and Drawings as FWF project I 3340-N35. A.P. supported by a Schrödinger fellowship of the FWF: J-3847-N35. J.T. partially supported by ERC Start grant no. (279307: Graph Games), FWF grant no. P23499-N23 and S11407-N23 (RiSE).","publication_status":"published","publisher":"Brown University","volume":26,"date_published":"2022-06-01T00:00:00Z","ec_funded":1,"oa_version":"Published Version","publication_identifier":{"issn":["1526-1719"]},"citation":{"ista":"Aichholzer O, Arroyo Guevara AM, Masárová Z, Parada I, Perz D, Pilz A, Tkadlec J, Vogtenhuber B. 2022. On compatible matchings. Journal of Graph Algorithms and Applications. 26(2), 225–240.","short":"O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz, J. Tkadlec, B. Vogtenhuber, Journal of Graph Algorithms and Applications 26 (2022) 225–240.","mla":"Aichholzer, Oswin, et al. “On Compatible Matchings.” <i>Journal of Graph Algorithms and Applications</i>, vol. 26, no. 2, Brown University, 2022, pp. 225–40, doi:<a href=\"https://doi.org/10.7155/jgaa.00591\">10.7155/jgaa.00591</a>.","ama":"Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings. <i>Journal of Graph Algorithms and Applications</i>. 2022;26(2):225-240. doi:<a href=\"https://doi.org/10.7155/jgaa.00591\">10.7155/jgaa.00591</a>","apa":"Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D., Pilz, A., … Vogtenhuber, B. (2022). On compatible matchings. <i>Journal of Graph Algorithms and Applications</i>. Brown University. <a href=\"https://doi.org/10.7155/jgaa.00591\">https://doi.org/10.7155/jgaa.00591</a>","ieee":"O. Aichholzer <i>et al.</i>, “On compatible matchings,” <i>Journal of Graph Algorithms and Applications</i>, vol. 26, no. 2. Brown University, pp. 225–240, 2022.","chicago":"Aichholzer, Oswin, Alan M Arroyo Guevara, Zuzana Masárová, Irene Parada, Daniel Perz, Alexander Pilz, Josef Tkadlec, and Birgit Vogtenhuber. “On Compatible Matchings.” <i>Journal of Graph Algorithms and Applications</i>. Brown University, 2022. <a href=\"https://doi.org/10.7155/jgaa.00591\">https://doi.org/10.7155/jgaa.00591</a>."},"department":[{"_id":"UlWa"},{"_id":"HeEd"},{"_id":"KrCh"}],"external_id":{"arxiv":["2101.03928"]},"language":[{"iso":"eng"}],"has_accepted_license":"1","issue":"2","_id":"11938","date_updated":"2026-04-16T09:18:20Z","article_processing_charge":"No","date_created":"2022-08-21T22:01:56Z","abstract":[{"lang":"eng","text":"A matching is compatible to two or more labeled point sets of size n with labels {1, . . . , n} if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled sets of n points in convex position there exists a compatible matching with ⌊√2n + 1 − 1⌋ edges. More generally, for any ℓ labeled point sets we construct compatible matchings of size Ω(n1/ℓ). As a corresponding upper bound, we use probabilistic arguments to show that for any ℓ given sets of n points there exists a labeling of each set such that the largest compatible matching has O(n2/(ℓ+1)) edges. Finally, we show that Θ(log n) copies of any set of n points are necessary and sufficient for the existence of labelings of these point sets such that any compatible matching consists only of a single edge."}],"type":"journal_article","oa":1,"file":[{"date_updated":"2022-08-22T06:42:42Z","access_level":"open_access","creator":"dernst","relation":"main_file","file_id":"11940","file_size":694538,"checksum":"dc6e255e3558faff924fd9e370886c11","success":1,"content_type":"application/pdf","date_created":"2022-08-22T06:42:42Z","file_name":"2022_JourGraphAlgorithmsApplic_Aichholzer.pdf"}],"corr_author":"1","status":"public","arxiv":1,"quality_controlled":"1","day":"01","scopus_import":"1","page":"225-240","project":[{"name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"},{"name":"Mathematics, Computer Science","_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"Z00342"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"grant_number":"S11407","call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory"}],"author":[{"first_name":"Oswin","last_name":"Aichholzer","full_name":"Aichholzer, Oswin"},{"last_name":"Arroyo Guevara","first_name":"Alan M","orcid":"0000-0003-2401-8670","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","full_name":"Arroyo Guevara, Alan M"},{"orcid":"0000-0002-6660-1322","last_name":"Masárová","first_name":"Zuzana","full_name":"Masárová, Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Parada","first_name":"Irene","full_name":"Parada, Irene"},{"full_name":"Perz, Daniel","last_name":"Perz","first_name":"Daniel"},{"full_name":"Pilz, Alexander","first_name":"Alexander","last_name":"Pilz"},{"first_name":"Josef","last_name":"Tkadlec","orcid":"0000-0002-1097-9684","full_name":"Tkadlec, Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Birgit","last_name":"Vogtenhuber","full_name":"Vogtenhuber, Birgit"}],"year":"2022","doi":"10.7155/jgaa.00591","article_type":"original","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"9296"}]},"ddc":["000"],"title":"On compatible matchings","month":"06"}]