Geodesic
On plane subgraphs of complete topological drawings
Ars Mathematica Contemporanea, Tome 20 (2021) no. 1, pp. 69-87.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

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 Dn of the complete graph Kn on 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 Dn with 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.
DOI : 10.26493/1855-3974.2226.e93
Keywords: Graph, topological drawing, plane subgraph, NP-complete problem 
@article{10_26493_1855_3974_2226_e93,
     author = {Alfredo Garc{\'\i}a Olaverri and Javier Tejel Altarriba and Alexander Pilz},
     title = {On plane subgraphs of complete topological drawings},
     journal = {Ars Mathematica Contemporanea},
     pages = {69--87},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2021},
     doi = {10.26493/1855-3974.2226.e93},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2226.e93/}
}
TY  - JOUR
AU  - Alfredo García Olaverri
AU  - Javier Tejel Altarriba
AU  - Alexander Pilz
TI  - On plane subgraphs of complete topological drawings
JO  - Ars Mathematica Contemporanea
PY  - 2021
SP  - 69
EP  - 87
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2226.e93/
DO  - 10.26493/1855-3974.2226.e93
LA  - en
ID  - 10_26493_1855_3974_2226_e93
ER  - 
%0 Journal Article
%A Alfredo García Olaverri
%A Javier Tejel Altarriba
%A Alexander Pilz
%T On plane subgraphs of complete topological drawings
%J Ars Mathematica Contemporanea
%D 2021
%P 69-87
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2226.e93/
%R 10.26493/1855-3974.2226.e93
%G en
%F 10_26493_1855_3974_2226_e93
Alfredo García Olaverri; Javier Tejel Altarriba; Alexander Pilz. On plane subgraphs of complete topological drawings. Ars Mathematica Contemporanea, Tome 20 (2021) no. 1, pp. 69-87. doi : 10.26493/1855-3974.2226.e93. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2226.e93/

Cité par Sources :