Twisted ways to find plane structures in simple drawings of complete graphs

Aichholzer, Oswin ; García, Alfredo ; Tejel, Javier (Universidad de Zaragoza) ; Vogtenhuber, Birgit ; Weinberger, Alexandra

Resumen: 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). 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.

Idioma: Inglés

DOI: 10.1007/s00454-023-00610-0

Año: 2024

Publicado en: DISCRETE & COMPUTATIONAL GEOMETRY 71 (2024), 40-66
ISSN: 0179-5376

Factor impacto JCR: 0.6 (2024)

Categ. JCR: MATHEMATICS rank: 282 / 483 = 0.584 (2024) - Q3 - T2
Categ. JCR: COMPUTER SCIENCE, THEORY & METHODS rank: 131 / 147 = 0.891 (2024) - Q4 - T3

Factor impacto SCIMAGO: 0.6 - Computational Theory and Mathematics (Q2) - Theoretical Computer Science (Q2) - Geometry and Topology (Q2) - Discrete Mathematics and Combinatorics (Q2)

Financiación: info:eu-repo/grantAgreement/ES/DGA/E41-17R
Financiación: info:eu-repo/grantAgreement/EC/H2020/734922/EU/Combinatorics of Networks and Computation/CONNECT
Financiación: info:eu-repo/grantAgreement/ES/MICIU-AEI/PID2019-104129GB-I00-AEI-10.13039-501100011033

Tipo y forma: Article (Published version)

Área (Departamento): Área Estadís. Investig. Opera. (Dpto. Métodos Estadísticos)