TY - JOUR

T1 - On plane subgraphs of complete topological drawings

AU - Olaverri, Alfredo García

AU - Altarriba, Javier Tejel

AU - Pilz, Alexander

N1 - Funding Information:
∗This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 734922. †Supported by MINECO project MTM2015-63791-R and Gobierno de Aragón Grant E41-17 (FEDER). ‡Supported by MINECO project MTM2015-63791-R, Gobierno de Aragón Grant E41-17 and project PID2019-104129GB-I00 / AEI / 10.13039/501100011033 of the Spanish Ministry of Science and Innovation. §Supported by a Schrödinger fellowship of the Austrian Science Fund (FWF): J-3847-N35. E-mail addresses: olaverri@unizar.es (Alfredo García Olaverri), jtejel@unizar.es (Javier Tejel Altarriba), apilz@ist.tugraz.at (Alexander Pilz)
Funding Information:
This project has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No. 734922.
Publisher Copyright:
© 2021 Society of Mathematicians, Physicists and Astronomers of Slovenia. All rights reserved.

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

KW - Graph

KW - NP-complete problem

KW - Plane subgraph

KW - Topological drawing

UR - http://www.scopus.com/inward/record.url?scp=85114040687&partnerID=8YFLogxK

U2 - 10.26493/1855-3974.2226.E93

DO - 10.26493/1855-3974.2226.E93

M3 - Article

AN - SCOPUS:85114040687

SN - 1855-3966

VL - 20

SP - 69

EP - 87

JO - Ars Mathematica Contemporanea

JF - Ars Mathematica Contemporanea

IS - 1

ER -