The 2-Page Crossing Number of K_n

Around 1958, Hill described how to draw the complete graph K_n with, crossings, and conjectured that the crossing number cr(K_n) is exactly Z(n). This is also known as Guy's conjecture as he later popularized it. Towards the end of the century, substantially different drawings of K_n with Z(n) crossings were found. These drawings are 2-page book drawings, that is, drawings where all the vertices are on a line ℓ (the spine) and each edge is fully contained in one of the two half-planes (pages) defined by ℓ. The 2-page crossing number of K_n, denoted by ν₂(K_n), is the minimum number of crossings determined by a 2-page book drawing of K_n. Since cr(K_n) ≤ ν₂(K_n) and ν₂(K_n) ≤ Z(n), a natural step towards Hill's Conjecture is the weaker conjecture ν₂(K_n) = Z(n), popularized by Vrt'o. In this paper we develop a new technique to investigate crossings in drawings of K_n, and use it to prove that ν₂(K_n) = Z(n). To this end, we extend the inherent geometric definition of k-edges for finite sets of points in the plane to topological drawings of K_n. We also introduce the concept of ≤≤ k-edges as a useful generalization of ≤k-edges and extend a powerful theorem that expresses the number of crossings in a rectilinear drawing of K_n in terms of its number of ≤k-edges to the topological setting. Finally, we give a complete characterization of crossing minimal 2-page book drawings of K_n and show that, up to equivalence, they are unique for n even, but that there exist an exponential number of non homeomorphic such drawings for n odd.