Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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


Edit:

Apparently there is a rather broad class of drawings with crossing number $Z(n)+O(n^3)$, which generalize the cylindrical drawings:

3) A spherical drawing is a drawing on the sphere where edges are drawn as shortest arcs.

Moon showed that a random spherical drawing of $K_n$ has expected crossing number $\frac{1}{64} n(n-1)(n-2)(n-3)$.

J. W. Moon, On the Distribution of Crossings in Random Complete Graphs, J. Soc. Indust. Appl. Math. 13 (1965), 506--510

I think the following construction must be known but I couldn't find any reference.

For $n$ even, if one places $n/2$ pairs of antipodal points on the sphere (so that no three pairs are on the same great circle), then the crossing number of the induced spherical drawing is $Z(n)+X(n)$ where the term $X(n)$ denotes the number of crossings of the $n/2$ arcs (half-circles) connecting the pairs of antipodal points (so $X(n) < n^2/8$). For the spherical analogue of cylindrical drawings, we have $X(n)=0$.

Question 2:

Is there some simple criterion for the positions of the pairs of antipodal vertices so that the half-circles can be drawn in a non-crossing way? Can one obtain, in this way, "antipodal" spherical drawings with $Z(n)$ crossings that are not cylindrical?

Question 3:

Dropping the condition that vertices should form antipodal pairs, are there spherical drawings with $Z(n)$ crossings that are not cylindrical?


Edit 2:

The antipodal spherical drawings can be generalized a bit:

3) An antipodal pseudospherical drawing: for even $n$, place $n/2$ pairs of vertices in the plane arbitrarily. Through every two pairs $(a_1, a_2)$ and $(b_1, b_2)$, draw a simple closed curve that visits the four points in the order $a_1,b_1,a_2,b_2$, and does not pass through other vertices. The curve represents four edges of $K_n$. Every two such curves cross precisely twice, either at vertices or at other points (the crossings of the emerging drawing of $K_n$). In particular, the curves form an arrangement of pseudocircles. Finally, for each pair $(a_1^i, a_2^i)$, select another pseudocircle $\rho_i$ passing through $a_1^i$ and $a_2^i$ and draw one of its segments $\gamma_i$ between $a_1^i$ and $a_2^i$, so that no two curves $\gamma_i$ and $\gamma_j$ cross.

From the three non-equivalent minimal drawings of $K_8$, the cylindrical and the $2$-page drawing are both antipodal pseudospherical drawings. The optimal $2$-page drawing of $K_{10}$ is not antipodal pseudospherical (it does not contain a perfect matching of edges $\gamma_i$: every such edge would have to have $6$ crossings).

Question 4:

For even $n\ge 10$, are there antipodal pseudospherical drawings of $K_n$ with $Z(n)$ crossings that are not cylindrical?

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.