000118720 001__ 118720
000118720 005__ 20230706131605.0
000118720 0247_ $$2doi$$a10.4230/LIPIcs.SoCG.2022.5
000118720 0248_ $$2sideral$$a129863
000118720 037__ $$aART-2022-129863
000118720 041__ $$aeng
000118720 100__ $$aAichholzer, Oswin
000118720 245__ $$aTwisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs
000118720 260__ $$c2022
000118720 5060_ $$aAccess copy available to the general public$$fUnrestricted
000118720 5203_ $$aSimple 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.
000118720 536__ $$9info:eu-repo/grantAgreement/ES/DGA/E41-17R$$9info:eu-repo/grantAgreement/EC/H2020/734922/EU/Combinatorics of Networks and Computation/CONNECT$$9This project has received funding from the European Union’s Horizon 2020 research and innovation program under grant agreement No H2020 734922-CONNECT$$9info:eu-repo/grantAgreement/ES/MICIU-AEI/PID2019-104129GB-I00-AEI-10.13039-501100011033
000118720 540__ $$9info:eu-repo/semantics/openAccess$$aby$$uhttp://creativecommons.org/licenses/by/3.0/es/
000118720 592__ $$a0.832$$b2022
000118720 593__ $$aSoftware$$c2022
000118720 593__ $$aLogic$$c2022
000118720 655_4 $$ainfo:eu-repo/semantics/article$$vinfo:eu-repo/semantics/publishedVersion
000118720 700__ $$0(orcid)0000-0002-6519-1472$$aGarcía, Alfredo$$uUniversidad de Zaragoza
000118720 700__ $$0(orcid)0000-0002-9543-7170$$aTejel, Javier$$uUniversidad de Zaragoza
000118720 700__ $$aVogtenhuber, Birgit
000118720 700__ $$aWeinberger, Alexandra
000118720 7102_ $$12007$$2265$$aUniversidad de Zaragoza$$bDpto. Métodos Estadísticos$$cÁrea Estadís. Investig. Opera.
000118720 773__ $$g224 (2022), 5 [18 pp.]$$pLeibniz int. proc. inform.$$tLeibniz international proceedings in informatics$$x1868-8969
000118720 8564_ $$s1189292$$uhttps://zaguan.unizar.es/record/118720/files/texto_completo.pdf$$yVersión publicada
000118720 8564_ $$s2001511$$uhttps://zaguan.unizar.es/record/118720/files/texto_completo.jpg?subformat=icon$$xicon$$yVersión publicada
000118720 909CO $$ooai:zaguan.unizar.es:118720$$particulos$$pdriver
000118720 951__ $$a2023-07-06-12:22:48
000118720 980__ $$aARTICLE