118720 20230706131605.0 doi 10.4230/LIPIcs.SoCG.2022.5 sideral 129863 ART-2022-129863 eng Aichholzer, Oswin Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs 2022 Access copy available to the general public Unrestricted Simple drawings are drawings of graphs in which the edges are Jordan arcs and each pair of edges share at most one point (a proper crossing or a common endpoint). We introduce a special kind of simple drawings that we call generalized twisted drawings. A simple drawing is generalized twisted if there is a point O such that every ray emanating from O crosses every edge of the drawing at most once and there is a ray emanating from O which crosses every edge exactly once. Via this new class of simple drawings, we show that every simple drawing of the complete graph with n vertices contains Ω(n^{1/2}) pairwise disjoint edges and a plane path of length Ω((log n)/(log log n)). Both results improve over previously known best lower bounds. On the way we show several structural results about and properties of generalized twisted drawings. We further present different characterizations of generalized twisted drawings, which might be of independent interest. info:eu-repo/grantAgreement/ES/DGA/E41-17R info:eu-repo/grantAgreement/EC/H2020/734922/EU/Combinatorics of Networks and Computation/CONNECT This project has received funding from the European Union’s Horizon 2020 research and innovation program under grant agreement No H2020 734922-CONNECT info:eu-repo/grantAgreement/ES/MICIU-AEI/PID2019-104129GB-I00-AEI-10.13039-501100011033 info:eu-repo/semantics/openAccess by http://creativecommons.org/licenses/by/3.0/es/ 0.832 2022 Software 2022 Logic 2022 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion García, Alfredo Universidad de Zaragoza (orcid)0000-0002-6519-1472 Tejel, Javier Universidad de Zaragoza (orcid)0000-0002-9543-7170 Vogtenhuber, Birgit Weinberger, Alexandra 2007 265 Universidad de Zaragoza Dpto. Métodos Estadísticos Área Estadís. Investig. Opera. 224 (2022), 5 [18 pp.] Leibniz int. proc. inform. Leibniz international proceedings in informatics 1868-8969 1189292 http://zaguan.unizar.es/record/118720/files/texto_completo.pdf Versión publicada 2001511 http://zaguan.unizar.es/record/118720/files/texto_completo.jpg?subformat=icon icon Versión publicada oai:zaguan.unizar.es:118720 articulos driver 2023-07-06-12:22:48 ARTICLE