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 -