Home  Issues  About JGAA  Instructions for Authors 
"Special issue on Selected papers from the Twentyeighth International Symposium on Graph Drawing and Network Visualization, GD 2020"
DOI: 10.7155/jgaa.00600
On the Maximum Number of Crossings in StarSimple Drawings of $K_n$ with No Empty Lens
Vol. 26, no. 3, pp. 381399, 2022. Regular paper.
Abstract A starsimple 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(n4)!$ is an upper bound on the number of crossings between two edges of a starsimple
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 starsimple drawings of the complete
graph $K_n$ with no empty lens. For a lower bound we construct a
starsimple drawing of $K_n$ with no empty lens in which a pair of edges
contributes $5^{n/22}$ crossings.
This work is licensed under the terms of the CCBY license.

Submitted: May 2021.
Reviewed: April 2022.
Revised: May 2022.
Accepted: June 2022.
Final: June 2022.
Published: June 2022.

Journal Supporters
