000132154 001__ 132154
000132154 005__ 20250923084414.0
000132154 0247_ $$2doi$$a10.1007/s00454-023-00610-0
000132154 0248_ $$2sideral$$a137381
000132154 037__ $$aART-2024-137381
000132154 041__ $$aeng
000132154 100__ $$aAichholzer, Oswin
000132154 245__ $$aTwisted ways to find plane structures in simple drawings of complete graphs
000132154 260__ $$c2024
000132154 5060_ $$aAccess copy available to the general public$$fUnrestricted
000132154 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). A simple drawing is c-monotone if there is a point O such that each ray emanating from O crosses each edge of the drawing at most once. We introduce a special kind of c-monotone drawings that we call generalized twisted drawings. A c-monotone drawing is generalized twisted if there is a ray emanating from O that crosses all the edges of the drawing. Via this class of drawings, we show that every simple drawing of the complete graph with n vertices contains [fórmula] pairwise disjoint edges and a plane cycle (and hence path) of length [fórmula]. Both results improve over best previously published lower bounds. On the way we show several structural results and properties of generalized twisted and c-monotone drawings, some of which we believe to be of independent interest. For example, we show that a drawing D is c-monotone if there exists a point O such that no edge of D is crossed more than once by any ray that emanates from O and passes through a vertex of D.
000132154 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
000132154 540__ $$9info:eu-repo/semantics/openAccess$$aby$$uhttp://creativecommons.org/licenses/by/3.0/es/
000132154 590__ $$a0.6$$b2024
000132154 592__ $$a0.6$$b2024
000132154 591__ $$aMATHEMATICS$$b282 / 483 = 0.584$$c2024$$dQ3$$eT2
000132154 593__ $$aComputational Theory and Mathematics$$c2024$$dQ2
000132154 591__ $$aCOMPUTER SCIENCE, THEORY & METHODS$$b131 / 147 = 0.891$$c2024$$dQ4$$eT3
000132154 593__ $$aTheoretical Computer Science$$c2024$$dQ2
000132154 593__ $$aGeometry and Topology$$c2024$$dQ2
000132154 593__ $$aDiscrete Mathematics and Combinatorics$$c2024$$dQ2
000132154 655_4 $$ainfo:eu-repo/semantics/article$$vinfo:eu-repo/semantics/publishedVersion
000132154 700__ $$0(orcid)0000-0002-6519-1472$$aGarcía, Alfredo
000132154 700__ $$0(orcid)0000-0002-9543-7170$$aTejel, Javier$$uUniversidad de Zaragoza
000132154 700__ $$aVogtenhuber, Birgit
000132154 700__ $$aWeinberger, Alexandra
000132154 7102_ $$12007$$2265$$aUniversidad de Zaragoza$$bDpto. Métodos Estadísticos$$cÁrea Estadís. Investig. Opera.
000132154 773__ $$g71 (2024), 40-66$$pDiscrete comput. geom.$$tDISCRETE & COMPUTATIONAL GEOMETRY$$x0179-5376
000132154 8564_ $$s807794$$uhttps://zaguan.unizar.es/record/132154/files/texto_completo.pdf$$yVersión publicada
000132154 8564_ $$s1064081$$uhttps://zaguan.unizar.es/record/132154/files/texto_completo.jpg?subformat=icon$$xicon$$yVersión publicada
000132154 909CO $$ooai:zaguan.unizar.es:132154$$particulos$$pdriver
000132154 951__ $$a2025-09-22-14:32:01
000132154 980__ $$aARTICLE