On plane subgraphs of complete topological drawings

García Olaverri A. (Universidad de Zaragoza) ; Tejel Altarriba J. (Universidad de Zaragoza) ; Pilz A.

Resumen: Topological drawings are representations of graphs in the plane, where vertices are represented by points, and edges by simple curves connecting the points. A drawing is simple if two edges intersect at most in a single point, either at a common endpoint or at a proper crossing. In this paper we study properties of maximal plane subgraphs of simple drawings Dnof the complete graph Knon n vertices. Our main structural result is that maximal plane subgraphs are 2-connected and what we call essentially 3-edge-connected. Besides, any maximal plane subgraph contains at least [3n/2] edges. We also address the problem of obtaining a plane subgraph of Dnwith the maximum number of edges, proving that this problem is NP-complete. However, given a plane spanning connected subgraph of Dn, a maximum plane augmentation of this subgraph can be found in O(n3) time. As a side result, we also show that the problem of finding a largest compatible plane straight-line graph of two labeled point sets is NP-complete. © 2021 Society of Mathematicians, Physicists and Astronomers of Slovenia. All rights reserved.

Idioma: Inglés

DOI: 10.26493/1855-3974.2226.E93

Año: 2021

Publicado en: Ars Mathematica Contemporanea 20, 1 (2021), 69-87
ISSN: 1855-3966

Factor impacto JCR: 0.922 (2021)

Categ. JCR: MATHEMATICS rank: 178 / 333 = 0.535 (2021) - Q3 - T2
Categ. JCR: MATHEMATICS, APPLIED rank: 213 / 267 = 0.798 (2021) - Q4 - T3

Factor impacto CITESCORE: 1.5 - Mathematics (Q3)

Factor impacto SCIMAGO: 0.741 - Algebra and Number Theory (Q2) - Theoretical Computer Science (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
Financiación: info:eu-repo/grantAgreement/ES/MINECO/MTM2015-63791-R

Tipo y forma: Article (Published version)

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