000110599 001__ 110599 000110599 005__ 20230519145613.0 000110599 0247_ $$2doi$$a10.26493/1855-3974.2226.E93 000110599 0248_ $$2sideral$$a127326 000110599 037__ $$aART-2021-127326 000110599 041__ $$aeng 000110599 100__ $$0(orcid)0000-0002-6519-1472$$aGarcía Olaverri A.$$uUniversidad de Zaragoza 000110599 245__ $$aOn plane subgraphs of complete topological drawings 000110599 260__ $$c2021 000110599 5060_ $$aAccess copy available to the general public$$fUnrestricted 000110599 5203_ $$aTopological 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. 000110599 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$$9info:eu-repo/grantAgreement/ES/MINECO/MTM2015-63791-R 000110599 540__ $$9info:eu-repo/semantics/openAccess$$aby$$uhttp://creativecommons.org/licenses/by/3.0/es/ 000110599 590__ $$a0.922$$b2021 000110599 592__ $$a0.741$$b2021 000110599 594__ $$a1.5$$b2021 000110599 591__ $$aMATHEMATICS$$b178 / 333 = 0.535$$c2021$$dQ3$$eT2 000110599 593__ $$aAlgebra and Number Theory$$c2021$$dQ2 000110599 591__ $$aMATHEMATICS, APPLIED$$b213 / 267 = 0.798$$c2021$$dQ4$$eT3 000110599 593__ $$aTheoretical Computer Science$$c2021$$dQ2 000110599 593__ $$aDiscrete Mathematics and Combinatorics$$c2021$$dQ2 000110599 655_4 $$ainfo:eu-repo/semantics/article$$vinfo:eu-repo/semantics/publishedVersion 000110599 700__ $$0(orcid)0000-0002-9543-7170$$aTejel Altarriba J.$$uUniversidad de Zaragoza 000110599 700__ $$aPilz A. 000110599 7102_ $$12007$$2265$$aUniversidad de Zaragoza$$bDpto. Métodos Estadísticos$$cÁrea Estadís. Investig. Opera. 000110599 773__ $$g20, 1 (2021), 69-87$$pARS MATHEMATICA CONTEMPORANEA$$tArs Mathematica Contemporanea$$x1855-3966 000110599 8564_ $$s1329155$$uhttps://zaguan.unizar.es/record/110599/files/texto_completo.pdf$$yVersión publicada 000110599 8564_ $$s1480467$$uhttps://zaguan.unizar.es/record/110599/files/texto_completo.jpg?subformat=icon$$xicon$$yVersión publicada 000110599 909CO $$ooai:zaguan.unizar.es:110599$$particulos$$pdriver 000110599 951__ $$a2023-05-18-16:09:24 000110599 980__ $$aARTICLE