110599 20230519145613.0 doi 10.26493/1855-3974.2226.E93 sideral 127326 ART-2021-127326 eng García Olaverri A. Universidad de Zaragoza (orcid)0000-0002-6519-1472 On plane subgraphs of complete topological drawings 2021 Access copy available to the general public Unrestricted 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. 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/grantAgreement/ES/MINECO/MTM2015-63791-R info:eu-repo/semantics/openAccess by http://creativecommons.org/licenses/by/3.0/es/ 0.922 2021 MATHEMATICS 178 / 333 = 0.535 2021 Q3 T2 MATHEMATICS, APPLIED 213 / 267 = 0.798 2021 Q4 T3 0.741 2021 Algebra and Number Theory 2021 Q2 Theoretical Computer Science 2021 Q2 Discrete Mathematics and Combinatorics 2021 Q2 1.5 2021 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion Tejel Altarriba J. Universidad de Zaragoza (orcid)0000-0002-9543-7170 Pilz A. 2007 265 Universidad de Zaragoza Dpto. Métodos Estadísticos Área Estadís. Investig. Opera. 20, 1 (2021), 69-87 ARS MATHEMATICA CONTEMPORANEA Ars Mathematica Contemporanea 1855-3966 1329155 http://zaguan.unizar.es/record/110599/files/texto_completo.pdf Versión publicada 1480467 http://zaguan.unizar.es/record/110599/files/texto_completo.jpg?subformat=icon icon Versión publicada oai:zaguan.unizar.es:110599 articulos driver 2023-05-18-16:09:24 ARTICLE