Skip to main content
2 of 6
edited body
Jan Kyncl
  • 6.1k
  • 1
  • 24
  • 31

Drawings of complete graphs with $Z(n)$ crossings

Hill conjectured that the minimum number of crossings in a drawing of the complete graph $K_n$ in the plane is exactly $$Z(n) = \frac{1}{4} \bigg\lfloor\frac{n}{2}\bigg\rfloor \left\lfloor\frac{n-1}{2}\right\rfloor \left\lfloor\frac{n-2}{2}\right\rfloor\left\lfloor\frac{n-3}{2}\right\rfloor.$$

In the literature, two general constructions of drawings of $K_n$ with $Z(n)$ crossings appear:

  1. the cylindrical (or tin can) drawing, where vertices are placed on the boundaries of the bottom and the top circular face of a cylinder and edges are drawn as geodesics,

  2. a $2$-page (or cycle) drawing where the vertices form a regular $n$-gon, with the diagonals that are "more horizontal than vertical" drawn inside the $n$-gon and the remaining diagonals drawn outside the $n$-gon. Recently Abrego et al. showed that all optimal $2$-page drawings of $K_n$ are basically the same (up to some boundary effects for odd $n$).

The question:

Are there other known classes of drawings of $K_n$ with $Z(n)$ crossings? I am especially interested in explicit constructions like the two above.

References:

B. M. Abrego, O. Aichholzer, S. Fernandez-Merchant, P. Ramos, and G. Salazar, The 2-page crossing number of $K_n$, 2012, arXiv:1206.5669

L. Beineke and R. Wilson, The early history of the brick factory problem, The Mathematical Intelligencer 32(2) (2010), 41--48

H. Harborth, Special numbers of crossings for complete graphs, Discrete Mathematics 244 (2002), 95--102

F. Harary and A. Hill, On the number of crossings in a complete graph, Proc. Edinburgh Math. Soc. (2) 13 (1963), 333--338

Jan Kyncl
  • 6.1k
  • 1
  • 24
  • 31