[{"external_id":{"arxiv":["2109.14892"]},"status":"public","citation":{"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>.","short":"A.M. Arroyo Guevara, S. Felsner, Journal of Graph Algorithms and Applications 27 (2023) 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>.","ista":"Arroyo Guevara AM, Felsner S. 2023. Approximating the bundled crossing number. Journal of Graph Algorithms and Applications. 27(6), 433–457.","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>"},"related_material":{"record":[{"relation":"earlier_version","id":"11185","status":"public"}]},"intvolume":"        27","has_accepted_license":"1","publication_status":"published","oa":1,"date_published":"2023-07-01T00:00:00Z","ddc":["510"],"year":"2023","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.","_id":"13969","type":"journal_article","oa_version":"Published Version","month":"07","date_updated":"2023-09-25T10:56:10Z","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."}],"page":"433-457","date_created":"2023-08-06T22:01:11Z","file_date_updated":"2023-08-07T08:00:48Z","volume":27,"project":[{"name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"754411"}],"issue":"6","language":[{"iso":"eng"}],"publication_identifier":{"issn":["1526-1719"]},"quality_controlled":"1","doi":"10.7155/jgaa.00629","department":[{"_id":"UlWa"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Brown University","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_type":"original","ec_funded":1,"scopus_import":"1","article_processing_charge":"Yes","publication":"Journal of Graph Algorithms and Applications","file":[{"file_name":"2023_JourGraphAlgorithms_Arroyo.pdf","success":1,"creator":"dernst","file_size":865774,"content_type":"application/pdf","relation":"main_file","checksum":"9c30d2b8e324cc1c904f2aeec92013a3","file_id":"13979","date_updated":"2023-08-07T08:00:48Z","access_level":"open_access","date_created":"2023-08-07T08:00:48Z"}],"day":"01","author":[{"full_name":"Arroyo Guevara, Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-2401-8670","first_name":"Alan M","last_name":"Arroyo Guevara"},{"first_name":"Stefan","last_name":"Felsner","full_name":"Felsner, Stefan"}],"arxiv":1,"title":"Approximating the bundled crossing number"},{"_id":"11999","year":"2023","acknowledgement":"This work was started during the 6th Austrian–Japanese–Mexican–Spanish Workshop on Discrete Geometry in June 2019 in Austria. We thank all the participants for the good atmosphere as well as discussions on the topic. Also, we thank Jan Kynčl for sending us remarks on a preliminary version of this work and an anonymous referee for further helpful comments.Alan Arroyo was funded by the Marie Skłodowska-Curie grant agreement No 754411. Fabian Klute was partially supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 612.001.651 and by the Austrian Science Fund (FWF): J-4510. Irene Parada and Birgit Vogtenhuber were partially supported by the Austrian Science Fund (FWF): W1230 and within the collaborative DACH project Arrangements and Drawings as FWF project I 3340-N35. Irene Parada was also partially supported by the Independent Research Fund Denmark grant 2020-2023 (9131-00044B) Dynamic Network Analysis and by the Margarita Salas Fellowship funded by the Ministry of Universities of Spain and the European Union (NextGenerationEU). Tilo Wiedera was supported by the German Research Foundation (DFG) grant CH 897/2-2.","date_created":"2022-08-28T22:02:01Z","file_date_updated":"2022-08-29T11:23:15Z","volume":69,"abstract":[{"lang":"eng","text":"A simple drawing D(G) of a graph G is one where each pair of edges share at most one point: either a common endpoint or a proper crossing. An edge e in the complement of G can be inserted into D(G) if there exists a simple drawing of G+e extending D(G). As a result of Levi’s Enlargement Lemma, if a drawing is rectilinear (pseudolinear), that is, the edges can be extended into an arrangement of lines (pseudolines), then any edge in the complement of G can be inserted. In contrast, we show that it is NP-complete to decide whether one edge can be inserted into a simple drawing. This remains true even if we assume that the drawing is pseudocircular, that is, the edges can be extended to an arrangement of pseudocircles. On the positive side, we show that, given an arrangement of pseudocircles A and a pseudosegment σ, it can be decided in polynomial time whether there exists a pseudocircle Φσ extending σ for which A∪{Φσ} is again an arrangement of pseudocircles."}],"date_updated":"2023-08-14T12:51:25Z","month":"04","type":"journal_article","oa_version":"Published Version","page":"745–770","citation":{"mla":"Arroyo Guevara, Alan M., et al. “Inserting One Edge into a Simple Drawing Is Hard.” <i>Discrete and Computational Geometry</i>, vol. 69, Springer Nature, 2023, pp. 745–770, doi:<a href=\"https://doi.org/10.1007/s00454-022-00394-9\">10.1007/s00454-022-00394-9</a>.","ista":"Arroyo Guevara AM, Klute F, Parada I, Vogtenhuber B, Seidel R, Wiedera T. 2023. Inserting one edge into a simple drawing is hard. Discrete and Computational Geometry. 69, 745–770.","apa":"Arroyo Guevara, A. M., Klute, F., Parada, I., Vogtenhuber, B., Seidel, R., &#38; Wiedera, T. (2023). Inserting one edge into a simple drawing is hard. <i>Discrete and Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-022-00394-9\">https://doi.org/10.1007/s00454-022-00394-9</a>","ama":"Arroyo Guevara AM, Klute F, Parada I, Vogtenhuber B, Seidel R, Wiedera T. Inserting one edge into a simple drawing is hard. <i>Discrete and Computational Geometry</i>. 2023;69:745–770. doi:<a href=\"https://doi.org/10.1007/s00454-022-00394-9\">10.1007/s00454-022-00394-9</a>","short":"A.M. Arroyo Guevara, F. Klute, I. Parada, B. Vogtenhuber, R. Seidel, T. Wiedera, Discrete and Computational Geometry 69 (2023) 745–770.","ieee":"A. M. Arroyo Guevara, F. Klute, I. Parada, B. Vogtenhuber, R. Seidel, and T. Wiedera, “Inserting one edge into a simple drawing is hard,” <i>Discrete and Computational Geometry</i>, vol. 69. Springer Nature, pp. 745–770, 2023.","chicago":"Arroyo Guevara, Alan M, Fabian Klute, Irene Parada, Birgit Vogtenhuber, Raimund Seidel, and Tilo Wiedera. “Inserting One Edge into a Simple Drawing Is Hard.” <i>Discrete and Computational Geometry</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00454-022-00394-9\">https://doi.org/10.1007/s00454-022-00394-9</a>."},"intvolume":"        69","status":"public","external_id":{"arxiv":["1909.07347"],"isi":["000840292800001"]},"date_published":"2023-04-01T00:00:00Z","ddc":["510"],"has_accepted_license":"1","oa":1,"publication_status":"published","ec_funded":1,"scopus_import":"1","article_processing_charge":"Yes (in subscription journal)","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_type":"original","publication":"Discrete and Computational Geometry","department":[{"_id":"UlWa"}],"publisher":"Springer Nature","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Inserting one edge into a simple drawing is hard","arxiv":1,"day":"01","file":[{"checksum":"def7ae3b28d9fd6aec16450e40090302","file_id":"12006","date_updated":"2022-08-29T11:23:15Z","access_level":"open_access","date_created":"2022-08-29T11:23:15Z","file_name":"2022_DiscreteandComputionalGeometry_Arroyo.pdf","success":1,"creator":"alisjak","file_size":1002218,"content_type":"application/pdf","relation":"main_file"}],"author":[{"orcid":"0000-0003-2401-8670","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","full_name":"Arroyo Guevara, Alan M","first_name":"Alan M","last_name":"Arroyo Guevara"},{"full_name":"Klute, Fabian","last_name":"Klute","first_name":"Fabian"},{"first_name":"Irene","last_name":"Parada","full_name":"Parada, Irene"},{"full_name":"Vogtenhuber, Birgit","last_name":"Vogtenhuber","first_name":"Birgit"},{"full_name":"Seidel, Raimund","first_name":"Raimund","last_name":"Seidel"},{"last_name":"Wiedera","first_name":"Tilo","full_name":"Wiedera, Tilo"}],"language":[{"iso":"eng"}],"isi":1,"project":[{"grant_number":"754411","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships"}],"quality_controlled":"1","doi":"10.1007/s00454-022-00394-9","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]}},{"date_published":"2022-03-16T00:00:00Z","main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.2109.14892"}],"publication_status":"published","oa":1,"related_material":{"record":[{"relation":"later_version","id":"13969","status":"public"}]},"intvolume":"     13174","citation":{"chicago":"Arroyo Guevara, Alan M, and Stefan Felsner. “Approximating the Bundled Crossing Number.” In <i>WALCOM 2022: Algorithms and Computation</i>, 13174:383–95. LNCS. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/978-3-030-96731-4_31\">https://doi.org/10.1007/978-3-030-96731-4_31</a>.","ieee":"A. M. Arroyo Guevara and S. Felsner, “Approximating the bundled crossing number,” in <i>WALCOM 2022: Algorithms and Computation</i>, Jember, Indonesia, 2022, vol. 13174, pp. 383–395.","short":"A.M. Arroyo Guevara, S. Felsner, in:, WALCOM 2022: Algorithms and Computation, Springer Nature, 2022, pp. 383–395.","ama":"Arroyo Guevara AM, Felsner S. Approximating the bundled crossing number. In: <i>WALCOM 2022: Algorithms and Computation</i>. Vol 13174. LNCS. Springer Nature; 2022:383-395. doi:<a href=\"https://doi.org/10.1007/978-3-030-96731-4_31\">10.1007/978-3-030-96731-4_31</a>","apa":"Arroyo Guevara, A. M., &#38; Felsner, S. (2022). Approximating the bundled crossing number. In <i>WALCOM 2022: Algorithms and Computation</i> (Vol. 13174, pp. 383–395). Jember, Indonesia: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-96731-4_31\">https://doi.org/10.1007/978-3-030-96731-4_31</a>","mla":"Arroyo Guevara, Alan M., and Stefan Felsner. “Approximating the Bundled Crossing Number.” <i>WALCOM 2022: Algorithms and Computation</i>, vol. 13174, Springer Nature, 2022, pp. 383–95, doi:<a href=\"https://doi.org/10.1007/978-3-030-96731-4_31\">10.1007/978-3-030-96731-4_31</a>.","ista":"Arroyo Guevara AM, Felsner S. 2022. Approximating the bundled crossing number. WALCOM 2022: Algorithms and Computation. WALCOM: Algorithms and ComputationLNCS vol. 13174, 383–395."},"status":"public","external_id":{"arxiv":["2109.14892"]},"volume":13174,"date_created":"2022-04-17T22:01:47Z","page":"383-395","oa_version":"Preprint","type":"conference","month":"03","abstract":[{"text":"Bundling crossings is a strategy which can enhance the readability of graph drawings. In this paper we consider bundlings for families of pseudosegments, i.e., simple curves such that any two have share at most one point at which they cross. Our main result is that there is a polynomial-time algorithm to compute an 8-approximation of the bundled crossing number of such instances (up to adding a term depending on the facial structure). This 8-approximation also holds for bundlings of good drawings of graphs. In the special case of circular drawings the approximation factor is 8 (no extra term), this improves upon the 10-approximation of Fink et al. [6]. We also show how to compute a 92-approximation when the intersection graph of the pseudosegments is bipartite.","lang":"eng"}],"date_updated":"2023-09-25T10:56:10Z","_id":"11185","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 Sklodowska Curie grant agreement No 754411. The second author has been supported by the German Research Foundation DFG Project FE 340/12-1.","year":"2022","doi":"10.1007/978-3-030-96731-4_31","quality_controlled":"1","publication_identifier":{"isbn":["9783030967307"],"eissn":["1611-3349"],"issn":["0302-9743"]},"conference":{"end_date":"2022-03-26","name":"WALCOM: Algorithms and Computation","location":"Jember, Indonesia","start_date":"2022-03-24"},"series_title":"LNCS","language":[{"iso":"eng"}],"project":[{"grant_number":"754411","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships"}],"arxiv":1,"title":"Approximating the bundled crossing number","author":[{"full_name":"Arroyo Guevara, Alan M","orcid":"0000-0003-2401-8670","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","first_name":"Alan M","last_name":"Arroyo Guevara"},{"last_name":"Felsner","first_name":"Stefan","full_name":"Felsner, Stefan"}],"day":"16","publication":"WALCOM 2022: Algorithms and Computation","ec_funded":1,"article_processing_charge":"No","scopus_import":"1","publisher":"Springer Nature","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"UlWa"}]},{"article_processing_charge":"No","ec_funded":1,"scopus_import":"1","article_type":"original","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"publication":"Journal of Graph Algorithms and Applications","department":[{"_id":"UlWa"},{"_id":"HeEd"},{"_id":"KrCh"}],"publisher":"Brown University","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","arxiv":1,"title":"On compatible matchings","day":"01","file":[{"success":1,"file_name":"2022_JourGraphAlgorithmsApplic_Aichholzer.pdf","creator":"dernst","content_type":"application/pdf","relation":"main_file","file_size":694538,"checksum":"dc6e255e3558faff924fd9e370886c11","date_updated":"2022-08-22T06:42:42Z","file_id":"11940","access_level":"open_access","date_created":"2022-08-22T06:42:42Z"}],"author":[{"last_name":"Aichholzer","first_name":"Oswin","full_name":"Aichholzer, Oswin"},{"orcid":"0000-0003-2401-8670","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","full_name":"Arroyo Guevara, Alan M","first_name":"Alan M","last_name":"Arroyo Guevara"},{"last_name":"Masárová","first_name":"Zuzana","full_name":"Masárová, Zuzana","orcid":"0000-0002-6660-1322","id":"45CFE238-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Irene","last_name":"Parada","full_name":"Parada, Irene"},{"full_name":"Perz, Daniel","last_name":"Perz","first_name":"Daniel"},{"full_name":"Pilz, Alexander","last_name":"Pilz","first_name":"Alexander"},{"orcid":"0000-0002-1097-9684","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","full_name":"Tkadlec, Josef","last_name":"Tkadlec","first_name":"Josef"},{"last_name":"Vogtenhuber","first_name":"Birgit","full_name":"Vogtenhuber, Birgit"}],"language":[{"iso":"eng"}],"issue":"2","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411"},{"name":"The Wittgenstein Prize","_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"Z00342"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"grant_number":"S11407","name":"Game Theory","call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","doi":"10.7155/jgaa.00591","publication_identifier":{"issn":["1526-1719"]},"_id":"11938","year":"2022","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).","date_created":"2022-08-21T22:01:56Z","file_date_updated":"2022-08-22T06:42:42Z","volume":26,"abstract":[{"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.","lang":"eng"}],"date_updated":"2023-02-23T13:54:21Z","month":"06","oa_version":"Published Version","type":"journal_article","page":"225-240","citation":{"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>.","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.","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>","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>","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.","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>."},"intvolume":"        26","related_material":{"record":[{"status":"public","id":"9296","relation":"earlier_version"}]},"external_id":{"arxiv":["2101.03928"]},"status":"public","ddc":["000"],"date_published":"2022-06-01T00:00:00Z","has_accepted_license":"1","oa":1,"publication_status":"published"},{"status":"public","external_id":{"arxiv":["2002.02287"],"isi":["000631693200001"]},"intvolume":"        97","citation":{"short":"A.M. Arroyo Guevara, D. Mcquillan, R.B. Richter, G. Salazar, M. Sullivan, Journal of Graph Theory 97 (2021) 426–440.","ieee":"A. M. Arroyo Guevara, D. Mcquillan, R. B. Richter, G. Salazar, and M. Sullivan, “Drawings of complete graphs in the projective plane,” <i>Journal of Graph Theory</i>, vol. 97, no. 3. Wiley, pp. 426–440, 2021.","chicago":"Arroyo Guevara, Alan M, Dan Mcquillan, R. Bruce Richter, Gelasio Salazar, and Matthew Sullivan. “Drawings of Complete Graphs in the Projective Plane.” <i>Journal of Graph Theory</i>. Wiley, 2021. <a href=\"https://doi.org/10.1002/jgt.22665\">https://doi.org/10.1002/jgt.22665</a>.","ista":"Arroyo Guevara AM, Mcquillan D, Richter RB, Salazar G, Sullivan M. 2021. Drawings of complete graphs in the projective plane. Journal of Graph Theory. 97(3), 426–440.","mla":"Arroyo Guevara, Alan M., et al. “Drawings of Complete Graphs in the Projective Plane.” <i>Journal of Graph Theory</i>, vol. 97, no. 3, Wiley, 2021, pp. 426–40, doi:<a href=\"https://doi.org/10.1002/jgt.22665\">10.1002/jgt.22665</a>.","apa":"Arroyo Guevara, A. M., Mcquillan, D., Richter, R. B., Salazar, G., &#38; Sullivan, M. (2021). Drawings of complete graphs in the projective plane. <i>Journal of Graph Theory</i>. Wiley. <a href=\"https://doi.org/10.1002/jgt.22665\">https://doi.org/10.1002/jgt.22665</a>","ama":"Arroyo Guevara AM, Mcquillan D, Richter RB, Salazar G, Sullivan M. Drawings of complete graphs in the projective plane. <i>Journal of Graph Theory</i>. 2021;97(3):426-440. doi:<a href=\"https://doi.org/10.1002/jgt.22665\">10.1002/jgt.22665</a>"},"publication_status":"published","oa":1,"date_published":"2021-03-23T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2002.02287"}],"acknowledgement":"We thank two reviewers for their corrections and suggestions on the original version of this\r\npaper. This project has received funding from NSERC Grant 50503-10940-500 and from the European Union’s Horizon 2020 research and innovation programme under the Marie SkłodowskaCurie grant agreement No 754411, IST, Klosterneuburg, Austria.","year":"2021","_id":"9295","page":"426-440","date_updated":"2023-08-07T14:26:15Z","abstract":[{"lang":"eng","text":"Hill's Conjecture states that the crossing number  cr(𝐾𝑛)  of the complete graph  𝐾𝑛  in the plane (equivalently, the sphere) is  14⌊𝑛2⌋⌊𝑛−12⌋⌊𝑛−22⌋⌊𝑛−32⌋=𝑛4/64+𝑂(𝑛3) . Moon proved that the expected number of crossings in a spherical drawing in which the points are randomly distributed and joined by geodesics is precisely  𝑛4/64+𝑂(𝑛3) , thus matching asymptotically the conjectured value of  cr(𝐾𝑛) . Let  cr𝑃(𝐺)  denote the crossing number of a graph  𝐺  in the projective plane. Recently, Elkies proved that the expected number of crossings in a naturally defined random projective plane drawing of  𝐾𝑛  is  (𝑛4/8𝜋2)+𝑂(𝑛3) . In analogy with the relation of Moon's result to Hill's conjecture, Elkies asked if  lim𝑛→∞ cr𝑃(𝐾𝑛)/𝑛4=1/8𝜋2 . We construct drawings of  𝐾𝑛  in the projective plane that disprove this."}],"type":"journal_article","oa_version":"Preprint","month":"03","volume":97,"date_created":"2021-03-28T22:01:41Z","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411"}],"isi":1,"language":[{"iso":"eng"}],"issue":"3","publication_identifier":{"eissn":["1097-0118"],"issn":["0364-9024"]},"doi":"10.1002/jgt.22665","quality_controlled":"1","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publisher":"Wiley","department":[{"_id":"UlWa"}],"publication":"Journal of Graph Theory","ec_funded":1,"article_processing_charge":"No","scopus_import":"1","article_type":"original","author":[{"last_name":"Arroyo Guevara","first_name":"Alan M","full_name":"Arroyo Guevara, Alan M","orcid":"0000-0003-2401-8670","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Dan","last_name":"Mcquillan","full_name":"Mcquillan, Dan"},{"first_name":"R. Bruce","last_name":"Richter","full_name":"Richter, R. Bruce"},{"first_name":"Gelasio","last_name":"Salazar","full_name":"Salazar, Gelasio"},{"first_name":"Matthew","last_name":"Sullivan","full_name":"Sullivan, Matthew"}],"day":"23","title":"Drawings of complete graphs in the projective plane","arxiv":1},{"alternative_title":["LNCS"],"external_id":{"arxiv":["2101.03928"]},"status":"public","intvolume":"     12635","related_material":{"record":[{"status":"public","id":"11938","relation":"later_version"}]},"citation":{"short":"O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz, J. Tkadlec, B. Vogtenhuber, in:, 15th International Conference on Algorithms and Computation, Springer Nature, 2021, pp. 221–233.","chicago":"Aichholzer, Oswin, Alan M Arroyo Guevara, Zuzana Masárová, Irene Parada, Daniel Perz, Alexander Pilz, Josef Tkadlec, and Birgit Vogtenhuber. “On Compatible Matchings.” In <i>15th International Conference on Algorithms and Computation</i>, 12635:221–33. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-68211-8_18\">https://doi.org/10.1007/978-3-030-68211-8_18</a>.","ieee":"O. Aichholzer <i>et al.</i>, “On compatible matchings,” in <i>15th International Conference on Algorithms and Computation</i>, Yangon, Myanmar, 2021, vol. 12635, pp. 221–233.","apa":"Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D., Pilz, A., … Vogtenhuber, B. (2021). On compatible matchings. In <i>15th International Conference on Algorithms and Computation</i> (Vol. 12635, pp. 221–233). Yangon, Myanmar: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-68211-8_18\">https://doi.org/10.1007/978-3-030-68211-8_18</a>","ista":"Aichholzer O, Arroyo Guevara AM, Masárová Z, Parada I, Perz D, Pilz A, Tkadlec J, Vogtenhuber B. 2021. On compatible matchings. 15th International Conference on Algorithms and Computation. WALCOM: Algorithms and Computation, LNCS, vol. 12635, 221–233.","mla":"Aichholzer, Oswin, et al. “On Compatible Matchings.” <i>15th International Conference on Algorithms and Computation</i>, vol. 12635, Springer Nature, 2021, pp. 221–33, doi:<a href=\"https://doi.org/10.1007/978-3-030-68211-8_18\">10.1007/978-3-030-68211-8_18</a>.","ama":"Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings. In: <i>15th International Conference on Algorithms and Computation</i>. Vol 12635. Springer Nature; 2021:221-233. doi:<a href=\"https://doi.org/10.1007/978-3-030-68211-8_18\">10.1007/978-3-030-68211-8_18</a>"},"oa":1,"publication_status":"published","date_published":"2021-02-16T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2101.03928"}],"acknowledgement":"A.A. funded by the Marie Skłodowska-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).","year":"2021","_id":"9296","page":"221-233","type":"conference","oa_version":"Preprint","month":"02","date_updated":"2023-02-21T16:33:44Z","abstract":[{"lang":"eng","text":" 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 convex sets of n points there exists a compatible matching with   ⌊2n−−√⌋  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   Θ(logn)  copies of any set of n points are necessary and sufficient for the existence of a labeling such that any compatible matching consists only of a single edge."}],"volume":12635,"date_created":"2021-03-28T22:01:41Z","project":[{"name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411"},{"_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"The Wittgenstein Prize","grant_number":"Z00342"},{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307"},{"grant_number":"P 23499-N23","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"grant_number":"S11407","call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory"}],"conference":{"end_date":"2021-03-02","start_date":"2021-02-28","location":"Yangon, Myanmar","name":"WALCOM: Algorithms and Computation"},"language":[{"iso":"eng"}],"publication_identifier":{"issn":["03029743"],"isbn":["9783030682101"],"eissn":["16113349"]},"doi":"10.1007/978-3-030-68211-8_18","quality_controlled":"1","publisher":"Springer Nature","user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","department":[{"_id":"UlWa"},{"_id":"HeEd"},{"_id":"KrCh"}],"publication":"15th International Conference on Algorithms and Computation","article_processing_charge":"No","ec_funded":1,"scopus_import":"1","author":[{"first_name":"Oswin","last_name":"Aichholzer","full_name":"Aichholzer, Oswin"},{"last_name":"Arroyo Guevara","first_name":"Alan M","full_name":"Arroyo Guevara, Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-2401-8670"},{"orcid":"0000-0002-6660-1322","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","full_name":"Masárová, Zuzana","last_name":"Masárová","first_name":"Zuzana"},{"first_name":"Irene","last_name":"Parada","full_name":"Parada, Irene"},{"first_name":"Daniel","last_name":"Perz","full_name":"Perz, Daniel"},{"full_name":"Pilz, Alexander","last_name":"Pilz","first_name":"Alexander"},{"last_name":"Tkadlec","first_name":"Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1097-9684","full_name":"Tkadlec, Josef"},{"full_name":"Vogtenhuber, Birgit","first_name":"Birgit","last_name":"Vogtenhuber"}],"day":"16","title":"On compatible matchings","arxiv":1},{"publication":"SIAM Journal on Discrete Mathematics","article_type":"original","scopus_import":"1","article_processing_charge":"No","ec_funded":1,"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publisher":"Society for Industrial and Applied Mathematics","department":[{"_id":"UlWa"}],"title":"Extending drawings of complete graphs into arrangements of pseudocircles","arxiv":1,"author":[{"first_name":"Alan M","last_name":"Arroyo Guevara","full_name":"Arroyo Guevara, Alan M","orcid":"0000-0003-2401-8670","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Richter, R. Bruce","last_name":"Richter","first_name":"R. Bruce"},{"last_name":"Sunohara","first_name":"Matthew","full_name":"Sunohara, Matthew"}],"day":"20","isi":1,"issue":"2","language":[{"iso":"eng"}],"project":[{"name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411"}],"doi":"10.1137/20M1313234","quality_controlled":"1","publication_identifier":{"issn":["08954801"]},"_id":"9468","year":"2021","volume":35,"date_created":"2021-06-06T22:01:30Z","page":"1050-1076","type":"journal_article","month":"05","oa_version":"Preprint","date_updated":"2023-08-08T13:58:12Z","abstract":[{"lang":"eng","text":"Motivated by the successful application of geometry to proving the Harary--Hill conjecture for “pseudolinear” drawings of $K_n$, we introduce “pseudospherical” drawings of graphs. A spherical drawing of a graph $G$ is a drawing in the unit sphere $\\mathbb{S}^2$ in which the vertices of $G$ are represented as points---no three on a great circle---and the edges of $G$ are shortest-arcs in $\\mathbb{S}^2$ connecting pairs of vertices. Such a drawing has three properties: (1) every edge $e$ is contained in a simple closed curve $\\gamma_e$ such that the only vertices in $\\gamma_e$ are the ends of $e$; (2) if $e\\ne f$, then $\\gamma_e\\cap\\gamma_f$ has precisely two crossings; and (3) if $e\\ne f$, then $e$ intersects $\\gamma_f$ at most once, in either a crossing or an end of $e$. We use properties (1)--(3) to define a pseudospherical drawing of $G$. Our main result is that for the complete graph, properties (1)--(3) are equivalent to the same three properties but with “precisely two crossings” in (2) replaced by “at most two crossings.” The proof requires a result in the geometric transversal theory of arrangements of pseudocircles. This is proved using the surprising result that the absence of special arcs (coherent spirals) in an arrangement of simple closed curves characterizes the fact that any two curves in the arrangement have at most two crossings. Our studies provide the necessary ideas for exhibiting a drawing of $K_{10}$ that has no extension to an arrangement of pseudocircles and a drawing of $K_9$ that does extend to an arrangement of pseudocircles, but no such extension has all pairs of pseudocircles crossing twice.\r\n"}],"intvolume":"        35","citation":{"ista":"Arroyo Guevara AM, Richter RB, Sunohara M. 2021. Extending drawings of complete graphs into arrangements of pseudocircles. SIAM Journal on Discrete Mathematics. 35(2), 1050–1076.","mla":"Arroyo Guevara, Alan M., et al. “Extending Drawings of Complete Graphs into Arrangements of Pseudocircles.” <i>SIAM Journal on Discrete Mathematics</i>, vol. 35, no. 2, Society for Industrial and Applied Mathematics, 2021, pp. 1050–76, doi:<a href=\"https://doi.org/10.1137/20M1313234\">10.1137/20M1313234</a>.","apa":"Arroyo Guevara, A. M., Richter, R. B., &#38; Sunohara, M. (2021). Extending drawings of complete graphs into arrangements of pseudocircles. <i>SIAM Journal on Discrete Mathematics</i>. Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/20M1313234\">https://doi.org/10.1137/20M1313234</a>","ama":"Arroyo Guevara AM, Richter RB, Sunohara M. Extending drawings of complete graphs into arrangements of pseudocircles. <i>SIAM Journal on Discrete Mathematics</i>. 2021;35(2):1050-1076. doi:<a href=\"https://doi.org/10.1137/20M1313234\">10.1137/20M1313234</a>","short":"A.M. Arroyo Guevara, R.B. Richter, M. Sunohara, SIAM Journal on Discrete Mathematics 35 (2021) 1050–1076.","ieee":"A. M. Arroyo Guevara, R. B. Richter, and M. Sunohara, “Extending drawings of complete graphs into arrangements of pseudocircles,” <i>SIAM Journal on Discrete Mathematics</i>, vol. 35, no. 2. Society for Industrial and Applied Mathematics, pp. 1050–1076, 2021.","chicago":"Arroyo Guevara, Alan M, R. Bruce Richter, and Matthew Sunohara. “Extending Drawings of Complete Graphs into Arrangements of Pseudocircles.” <i>SIAM Journal on Discrete Mathematics</i>. Society for Industrial and Applied Mathematics, 2021. <a href=\"https://doi.org/10.1137/20M1313234\">https://doi.org/10.1137/20M1313234</a>."},"external_id":{"isi":["000674142200022"],"arxiv":["2001.06053"]},"status":"public","date_published":"2021-05-20T00:00:00Z","main_file_link":[{"url":"https://arxiv.org/abs/2001.06053","open_access":"1"}],"oa":1,"publication_status":"published"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"UlWa"}],"publication":"36th International Symposium on Computational Geometry","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"ec_funded":1,"scopus_import":"1","article_processing_charge":"No","author":[{"id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-2401-8670","full_name":"Arroyo Guevara, Alan M","first_name":"Alan M","last_name":"Arroyo Guevara"},{"first_name":"Julien","last_name":"Bensmail","full_name":"Bensmail, Julien"},{"full_name":"Bruce Richter, R.","last_name":"Bruce Richter","first_name":"R."}],"file":[{"checksum":"93571b76cf97d5b7c8aabaeaa694dd7e","file_id":"8006","date_updated":"2020-07-14T12:48:06Z","access_level":"open_access","date_created":"2020-06-23T11:06:23Z","file_name":"2020_LIPIcsSoCG_Arroyo.pdf","creator":"dernst","file_size":592661,"content_type":"application/pdf","relation":"main_file"}],"day":"01","article_number":"9:1 - 9:14","arxiv":1,"title":"Extending drawings of graphs to arrangements of pseudolines","project":[{"name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"754411"}],"conference":{"end_date":"2020-06-26","start_date":"2020-06-22","name":"SoCG: Symposium on Computational Geometry","location":"Zürich, Switzerland"},"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9783959771436"],"issn":["18688969"]},"doi":"10.4230/LIPIcs.SoCG.2020.9","quality_controlled":"1","year":"2020","_id":"7994","month":"06","oa_version":"Published Version","type":"conference","abstract":[{"lang":"eng","text":"In the recent study of crossing numbers, drawings of graphs that can be extended to an arrangement of pseudolines (pseudolinear drawings) have played an important role as they are a natural combinatorial extension of rectilinear (or straight-line) drawings. A characterization of the pseudolinear drawings of K_n was found recently. We extend this characterization to all graphs, by describing the set of minimal forbidden subdrawings for pseudolinear drawings. Our characterization also leads to a polynomial-time algorithm to recognize pseudolinear drawings and construct the pseudolines when it is possible."}],"date_updated":"2023-02-23T13:22:12Z","volume":164,"date_created":"2020-06-22T09:14:21Z","file_date_updated":"2020-07-14T12:48:06Z","alternative_title":["LIPIcs"],"external_id":{"arxiv":["1804.09317"]},"status":"public","intvolume":"       164","citation":{"short":"A.M. Arroyo Guevara, J. Bensmail, R. Bruce Richter, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","chicago":"Arroyo Guevara, Alan M, Julien Bensmail, and R. Bruce Richter. “Extending Drawings of Graphs to Arrangements of Pseudolines.” In <i>36th International Symposium on Computational Geometry</i>, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.9\">https://doi.org/10.4230/LIPIcs.SoCG.2020.9</a>.","ieee":"A. M. Arroyo Guevara, J. Bensmail, and R. Bruce Richter, “Extending drawings of graphs to arrangements of pseudolines,” in <i>36th International Symposium on Computational Geometry</i>, Zürich, Switzerland, 2020, vol. 164.","apa":"Arroyo Guevara, A. M., Bensmail, J., &#38; Bruce Richter, R. (2020). Extending drawings of graphs to arrangements of pseudolines. In <i>36th International Symposium on Computational Geometry</i> (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.9\">https://doi.org/10.4230/LIPIcs.SoCG.2020.9</a>","ista":"Arroyo Guevara AM, Bensmail J, Bruce Richter R. 2020. Extending drawings of graphs to arrangements of pseudolines. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 9:1-9:14.","mla":"Arroyo Guevara, Alan M., et al. “Extending Drawings of Graphs to Arrangements of Pseudolines.” <i>36th International Symposium on Computational Geometry</i>, vol. 164, 9:1-9:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.9\">10.4230/LIPIcs.SoCG.2020.9</a>.","ama":"Arroyo Guevara AM, Bensmail J, Bruce Richter R. Extending drawings of graphs to arrangements of pseudolines. In: <i>36th International Symposium on Computational Geometry</i>. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.9\">10.4230/LIPIcs.SoCG.2020.9</a>"},"publication_status":"published","oa":1,"has_accepted_license":"1","date_published":"2020-06-01T00:00:00Z","ddc":["510"]},{"date_updated":"2023-09-05T15:09:16Z","abstract":[{"lang":"eng","text":"A simple drawing D(G) of a graph G is one where each pair of edges share at most one point: either a common endpoint or a proper crossing. An edge e in the complement of G can be inserted into D(G) if there exists a simple drawing of   G+e  extending D(G). As a result of Levi’s Enlargement Lemma, if a drawing is rectilinear (pseudolinear), that is, the edges can be extended into an arrangement of lines (pseudolines), then any edge in the complement of G can be inserted. In contrast, we show that it is   NP -complete to decide whether one edge can be inserted into a simple drawing. This remains true even if we assume that the drawing is pseudocircular, that is, the edges can be extended to an arrangement of pseudocircles. On the positive side, we show that, given an arrangement of pseudocircles   A  and a pseudosegment   σ , it can be decided in polynomial time whether there exists a pseudocircle   Φσ  extending   σ  for which   A∪{Φσ}  is again an arrangement of pseudocircles."}],"type":"conference","month":"10","oa_version":"None","page":"325-338","date_created":"2020-11-06T08:45:03Z","volume":12301,"year":"2020","_id":"8732","publication_status":"published","date_published":"2020-10-09T00:00:00Z","status":"public","alternative_title":["LNCS"],"citation":{"apa":"Arroyo Guevara, A. M., Klute, F., Parada, I., Seidel, R., Vogtenhuber, B., &#38; Wiedera, T. (2020). Inserting one edge into a simple drawing is hard. In <i>Graph-Theoretic Concepts in Computer Science</i> (Vol. 12301, pp. 325–338). Leeds, United Kingdom: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-60440-0_26\">https://doi.org/10.1007/978-3-030-60440-0_26</a>","mla":"Arroyo Guevara, Alan M., et al. “Inserting One Edge into a Simple Drawing Is Hard.” <i>Graph-Theoretic Concepts in Computer Science</i>, vol. 12301, Springer Nature, 2020, pp. 325–38, doi:<a href=\"https://doi.org/10.1007/978-3-030-60440-0_26\">10.1007/978-3-030-60440-0_26</a>.","ista":"Arroyo Guevara AM, Klute F, Parada I, Seidel R, Vogtenhuber B, Wiedera T. 2020. Inserting one edge into a simple drawing is hard. Graph-Theoretic Concepts in Computer Science. WG: Workshop on Graph-Theoretic Concepts in Computer Science, LNCS, vol. 12301, 325–338.","ama":"Arroyo Guevara AM, Klute F, Parada I, Seidel R, Vogtenhuber B, Wiedera T. Inserting one edge into a simple drawing is hard. In: <i>Graph-Theoretic Concepts in Computer Science</i>. Vol 12301. Springer Nature; 2020:325-338. doi:<a href=\"https://doi.org/10.1007/978-3-030-60440-0_26\">10.1007/978-3-030-60440-0_26</a>","short":"A.M. Arroyo Guevara, F. Klute, I. Parada, R. Seidel, B. Vogtenhuber, T. Wiedera, in:, Graph-Theoretic Concepts in Computer Science, Springer Nature, 2020, pp. 325–338.","chicago":"Arroyo Guevara, Alan M, Fabian Klute, Irene Parada, Raimund Seidel, Birgit Vogtenhuber, and Tilo Wiedera. “Inserting One Edge into a Simple Drawing Is Hard.” In <i>Graph-Theoretic Concepts in Computer Science</i>, 12301:325–38. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/978-3-030-60440-0_26\">https://doi.org/10.1007/978-3-030-60440-0_26</a>.","ieee":"A. M. Arroyo Guevara, F. Klute, I. Parada, R. Seidel, B. Vogtenhuber, and T. Wiedera, “Inserting one edge into a simple drawing is hard,” in <i>Graph-Theoretic Concepts in Computer Science</i>, Leeds, United Kingdom, 2020, vol. 12301, pp. 325–338."},"intvolume":"     12301","day":"09","author":[{"first_name":"Alan M","last_name":"Arroyo Guevara","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-2401-8670","full_name":"Arroyo Guevara, Alan M"},{"full_name":"Klute, Fabian","last_name":"Klute","first_name":"Fabian"},{"full_name":"Parada, Irene","last_name":"Parada","first_name":"Irene"},{"first_name":"Raimund","last_name":"Seidel","full_name":"Seidel, Raimund"},{"full_name":"Vogtenhuber, Birgit","first_name":"Birgit","last_name":"Vogtenhuber"},{"last_name":"Wiedera","first_name":"Tilo","full_name":"Wiedera, Tilo"}],"title":"Inserting one edge into a simple drawing is hard","department":[{"_id":"UlWa"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publisher":"Springer Nature","article_processing_charge":"No","ec_funded":1,"scopus_import":"1","publication":"Graph-Theoretic Concepts in Computer Science","publication_identifier":{"issn":["0302-9743"],"isbn":["9783030604394","9783030604400"],"eissn":["1611-3349"]},"quality_controlled":"1","doi":"10.1007/978-3-030-60440-0_26","project":[{"grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"language":[{"iso":"eng"}],"conference":{"start_date":"2020-06-24","name":"WG: Workshop on Graph-Theoretic Concepts in Computer Science","location":"Leeds, United Kingdom","end_date":"2020-06-26"}},{"oa":1,"publication_status":"published","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1901.09955"}],"date_published":"2019-11-01T00:00:00Z","status":"public","external_id":{"arxiv":["1901.09955"],"isi":["000486358100025"]},"citation":{"ieee":"A. Silva, A. M. Arroyo Guevara, B. Richter, and O. Lee, “Graphs with at most one crossing,” <i>Discrete Mathematics</i>, vol. 342, no. 11. Elsevier, pp. 3201–3207, 2019.","chicago":"Silva, André , Alan M Arroyo Guevara, Bruce Richter, and Orlando Lee. “Graphs with at Most One Crossing.” <i>Discrete Mathematics</i>. Elsevier, 2019. <a href=\"https://doi.org/10.1016/j.disc.2019.06.031\">https://doi.org/10.1016/j.disc.2019.06.031</a>.","short":"A. Silva, A.M. Arroyo Guevara, B. Richter, O. Lee, Discrete Mathematics 342 (2019) 3201–3207.","ama":"Silva A, Arroyo Guevara AM, Richter B, Lee O. Graphs with at most one crossing. <i>Discrete Mathematics</i>. 2019;342(11):3201-3207. doi:<a href=\"https://doi.org/10.1016/j.disc.2019.06.031\">10.1016/j.disc.2019.06.031</a>","mla":"Silva, André, et al. “Graphs with at Most One Crossing.” <i>Discrete Mathematics</i>, vol. 342, no. 11, Elsevier, 2019, pp. 3201–07, doi:<a href=\"https://doi.org/10.1016/j.disc.2019.06.031\">10.1016/j.disc.2019.06.031</a>.","ista":"Silva A, Arroyo Guevara AM, Richter B, Lee O. 2019. Graphs with at most one crossing. Discrete Mathematics. 342(11), 3201–3207.","apa":"Silva, A., Arroyo Guevara, A. M., Richter, B., &#38; Lee, O. (2019). Graphs with at most one crossing. <i>Discrete Mathematics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.disc.2019.06.031\">https://doi.org/10.1016/j.disc.2019.06.031</a>"},"intvolume":"       342","type":"journal_article","oa_version":"Preprint","month":"11","date_updated":"2023-08-29T06:31:41Z","abstract":[{"lang":"eng","text":"The crossing number of a graph G is the least number of crossings over all possible drawings of G. We present a structural characterization of graphs with crossing number one."}],"page":"3201-3207","date_created":"2019-07-14T21:59:20Z","volume":342,"year":"2019","_id":"6638","publication_identifier":{"issn":["0012-365X"]},"quality_controlled":"1","doi":"10.1016/j.disc.2019.06.031","project":[{"_id":"26366136-B435-11E9-9278-68D0E5697425","name":"Reglas de Conectividad funcional en el hipocampo"},{"name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"754411"}],"issue":"11","language":[{"iso":"eng"}],"isi":1,"day":"01","author":[{"first_name":"André ","last_name":"Silva","full_name":"Silva, André "},{"id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-2401-8670","full_name":"Arroyo Guevara, Alan M","first_name":"Alan M","last_name":"Arroyo Guevara"},{"full_name":"Richter, Bruce","last_name":"Richter","first_name":"Bruce"},{"last_name":"Lee","first_name":"Orlando","full_name":"Lee, Orlando"}],"title":"Graphs with at most one crossing","arxiv":1,"department":[{"_id":"UlWa"}],"publisher":"Elsevier","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","article_processing_charge":"No","scopus_import":"1","ec_funded":1,"publication":"Discrete Mathematics"},{"year":"2019","_id":"7230","type":"conference","month":"11","oa_version":"Preprint","date_updated":"2023-09-06T14:56:00Z","abstract":[{"lang":"eng","text":"Simple drawings of graphs are those in which each pair of edges share at most one point, either a common endpoint or a proper crossing. In this paper we study the problem of extending a simple drawing D(G) of a graph G by inserting a set of edges from the complement of G into D(G) such that the result is a simple drawing. In the context of rectilinear drawings, the problem is trivial. For pseudolinear drawings, the existence of such an extension follows from Levi’s enlargement lemma. In contrast, we prove that deciding if a given set of edges can be inserted into a simple drawing is NP-complete. Moreover, we show that the maximization version of the problem is APX-hard. We also present a polynomial-time algorithm for deciding whether one edge uv can be inserted into D(G) when {u,v} is a dominating set for the graph G."}],"page":"230-243","date_created":"2020-01-05T23:00:47Z","volume":11904,"status":"public","external_id":{"arxiv":["1908.08129"],"isi":["000612918800018"]},"alternative_title":["LNCS"],"citation":{"mla":"Arroyo Guevara, Alan M., et al. “Extending Simple Drawings.” <i>27th International Symposium on Graph Drawing and Network Visualization</i>, vol. 11904, Springer Nature, 2019, pp. 230–43, doi:<a href=\"https://doi.org/10.1007/978-3-030-35802-0_18\">10.1007/978-3-030-35802-0_18</a>.","ista":"Arroyo Guevara AM, Derka M, Parada I. 2019. Extending simple drawings. 27th International Symposium on Graph Drawing and Network Visualization. GD: Graph Drawing and Network Visualization, LNCS, vol. 11904, 230–243.","apa":"Arroyo Guevara, A. M., Derka, M., &#38; Parada, I. (2019). Extending simple drawings. In <i>27th International Symposium on Graph Drawing and Network Visualization</i> (Vol. 11904, pp. 230–243). Prague, Czech Republic: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-35802-0_18\">https://doi.org/10.1007/978-3-030-35802-0_18</a>","ama":"Arroyo Guevara AM, Derka M, Parada I. Extending simple drawings. In: <i>27th International Symposium on Graph Drawing and Network Visualization</i>. Vol 11904. Springer Nature; 2019:230-243. doi:<a href=\"https://doi.org/10.1007/978-3-030-35802-0_18\">10.1007/978-3-030-35802-0_18</a>","short":"A.M. Arroyo Guevara, M. Derka, I. Parada, in:, 27th International Symposium on Graph Drawing and Network Visualization, Springer Nature, 2019, pp. 230–243.","ieee":"A. M. Arroyo Guevara, M. Derka, and I. Parada, “Extending simple drawings,” in <i>27th International Symposium on Graph Drawing and Network Visualization</i>, Prague, Czech Republic, 2019, vol. 11904, pp. 230–243.","chicago":"Arroyo Guevara, Alan M, Martin Derka, and Irene Parada. “Extending Simple Drawings.” In <i>27th International Symposium on Graph Drawing and Network Visualization</i>, 11904:230–43. Springer Nature, 2019. <a href=\"https://doi.org/10.1007/978-3-030-35802-0_18\">https://doi.org/10.1007/978-3-030-35802-0_18</a>."},"intvolume":"     11904","oa":1,"publication_status":"published","main_file_link":[{"url":"https://arxiv.org/abs/1908.08129","open_access":"1"}],"date_published":"2019-11-28T00:00:00Z","department":[{"_id":"UlWa"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publisher":"Springer Nature","article_processing_charge":"No","ec_funded":1,"scopus_import":"1","publication":"27th International Symposium on Graph Drawing and Network Visualization","day":"28","author":[{"full_name":"Arroyo Guevara, Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-2401-8670","last_name":"Arroyo Guevara","first_name":"Alan M"},{"full_name":"Derka, Martin","last_name":"Derka","first_name":"Martin"},{"full_name":"Parada, Irene","first_name":"Irene","last_name":"Parada"}],"arxiv":1,"title":"Extending simple drawings","project":[{"call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411"}],"language":[{"iso":"eng"}],"conference":{"start_date":"2019-09-17","location":"Prague, Czech Republic","name":"GD: Graph Drawing and Network Visualization","end_date":"2019-09-20"},"isi":1,"publication_identifier":{"eissn":["1611-3349"],"isbn":["978-3-0303-5801-3"],"issn":["0302-9743"]},"quality_controlled":"1","doi":"10.1007/978-3-030-35802-0_18"}]