Geodesic
Saturated simple and 2-simple topological graphs with few edges
Journal of Graph Algorithms and Applications, Special Issue on Graph Drawing Beyond Planarity , Tome 22 (2018) no. 1, pp. 117-138.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

A simple topological graph is a topological graph in which any two edges have at most one common point, which is either their common endpoint or a proper crossing. More generally, in a $k$-simple topological graph, every pair of edges has at most $k$ common points of this kind. We construct saturated simple and 2-simple graphs with few edges. These are $k$-simple graphs in which no further edge can be added. We improve the previous upper bounds of Kynčl, Pach, Radoičić, and Tóth [Comput. Geom., 48, 2015] and show that there are saturated simple graphs on $n$ vertices with only $7n$ edges and saturated 2-simple graphs on $n$ vertices with $14.5n$ edges. As a consequence, there is a $k$-simple graph (for a general $k$), which can be saturated using $14.5n$ edges, while previous upper bounds suggested $17.5n$ edges. We also construct saturated simple and 2-simple graphs that have some vertices with low degree. 
@article{JGAA_2018_22_1_a7,
     author = {P\'eter Hajnal and Alexander Igamberdiev and G\"unter Rote and Andr\'e Schulz},
     title = {Saturated simple and 2-simple topological graphs with few edges},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {117--138},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2018},
     doi = {10.7155/jgaa.00460},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00460/}
}
TY  - JOUR
AU  - Péter Hajnal
AU  - Alexander Igamberdiev
AU  - Günter Rote
AU  - André Schulz
TI  - Saturated simple and 2-simple topological graphs with few edges
JO  - Journal of Graph Algorithms and Applications
PY  - 2018
SP  - 117
EP  - 138
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00460/
DO  - 10.7155/jgaa.00460
LA  - en
ID  - JGAA_2018_22_1_a7
ER  - 
%0 Journal Article
%A Péter Hajnal
%A Alexander Igamberdiev
%A Günter Rote
%A André Schulz
%T Saturated simple and 2-simple topological graphs with few edges
%J Journal of Graph Algorithms and Applications
%D 2018
%P 117-138
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00460/
%R 10.7155/jgaa.00460
%G en
%F JGAA_2018_22_1_a7
Péter Hajnal; Alexander Igamberdiev; Günter Rote; André Schulz. Saturated simple and 2-simple topological graphs with few edges. Journal of Graph Algorithms and Applications, 
							Special Issue on Graph Drawing Beyond Planarity
					, Tome 22 (2018) no. 1, pp. 117-138. doi : 10.7155/jgaa.00460. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00460/

Cité par Sources :