Return to Question

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. Every two such curves cross precisely twice, either at vertices or at other points (that become the crossings of the emerging drawing of $K_n$). That is, 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$ to $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, since it does not contain a perfect matching of edges, each with $6$ crossings.

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).

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. Every two such curves cross precisely twice, either at vertices or at other points (that become the crossings of the emerging drawing of $K_n$). That is, 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$ to $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, since it does not contain a perfect matching of edges, each with $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?

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, spherical drawings with $Z(n)$ crossings that are not cylindrical?

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?