Home Issues About JGAA Instructions for Authors
 
 
Special issue on Selected papers from the Twenty-eighth International Symposium on Graph Drawing and Network Visualization, GD 2020
DOI: 10.7155/jgaa.00600
On the Maximum Number of Crossings in Star-Simple Drawings of $K_n$ with No Empty Lens
Vol. 26, no. 3, pp. 381-399, 2022. Regular paper.
Abstract 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.
 This work is licensed under the terms of the CC-BY license.
Submitted: May 2021.
Reviewed: April 2022.
Revised: May 2022.
Accepted: June 2022.
Final: June 2022.
Published: June 2022.
Communicated by David Auber and Pavel Valtr
article (PDF)
BibTeX