Geodesic
On the Maximum Number of Crossings in Star-Simple Drawings of $K_n$ with No Empty Lens
Journal of Graph Algorithms and Applications, Special issue on Selected papers from the Twenty-eighth International Symposium on Graph Drawing and Network Visualization, GD 2020 , Tome 26 (2022) no. 3, pp. 381-399.

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

A star-simple drawing of a graph is a drawing in which adjacent edges do not cross. In contrast, there is no restriction on the number of crossings between two independent edges. We forbid empty lenses, i.e., every lens is required to enclose a vertex, and show that with this restriction $3\cdot(n-4)!$ is an upper bound on the number of crossings between two edges of a star-simple drawing of $K_n$. It follows that $n!$ bounds the total number of crossings in the drawing. This is the first finite upper bound on the number of crossings in star-simple drawings of the complete graph $K_n$ with no empty lens. For a lower bound we construct a star-simple drawing of $K_n$ with no empty lens in which a pair of edges contributes $5^{n/2-2}$ crossings. 
@article{JGAA_2022_26_3_a6,
     author = {Stefan Felsner and Michael Hoffmann and Kristin Knorr and Jan Kyn\v{c}l and Irene Parada},
     title = {On the {Maximum} {Number} of {Crossings} in {Star-Simple} {Drawings} of $K_n$ with {No} {Empty} {Lens}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {381--399},
     publisher = {mathdoc},
     volume = {26},
     number = {3},
     year = {2022},
     doi = {10.7155/jgaa.00600},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00600/}
}
TY  - JOUR
AU  - Stefan Felsner
AU  - Michael Hoffmann
AU  - Kristin Knorr
AU  - Jan Kynčl
AU  - Irene Parada
TI  - On the Maximum Number of Crossings in Star-Simple Drawings of $K_n$ with No Empty Lens
JO  - Journal of Graph Algorithms and Applications
PY  - 2022
SP  - 381
EP  - 399
VL  - 26
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00600/
DO  - 10.7155/jgaa.00600
LA  - en
ID  - JGAA_2022_26_3_a6
ER  - 
%0 Journal Article
%A Stefan Felsner
%A Michael Hoffmann
%A Kristin Knorr
%A Jan Kynčl
%A Irene Parada
%T On the Maximum Number of Crossings in Star-Simple Drawings of $K_n$ with No Empty Lens
%J Journal of Graph Algorithms and Applications
%D 2022
%P 381-399
%V 26
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00600/
%R 10.7155/jgaa.00600
%G en
%F JGAA_2022_26_3_a6
Stefan Felsner; Michael Hoffmann; Kristin Knorr; Jan Kynčl; Irene Parada. On the Maximum Number of Crossings in Star-Simple Drawings of $K_n$ with No Empty Lens. Journal of Graph Algorithms and Applications, 
							Special issue on Selected papers from the Twenty-eighth International Symposium on Graph Drawing and Network Visualization, GD 2020
					, Tome 26 (2022) no. 3, pp. 381-399. doi : 10.7155/jgaa.00600. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00600/

Cité par Sources :