2012/06/17 by Bernardo M. Ábrego, Oswin Aichholzer, Silvia Fernández‐Merchant +2 · 1 citation
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #Topological and Geometric Data Analysis #Combinatorics #Conjecture #Mathematics #Crossing number (knot theory) #Discrete mathematics
paper · doi:10.1145/2261250.2261310
openalex publication_date 2012/06/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
Around 1958, Hill conjectured that the crossing number CRg(Kn) of the complete graph KKn is Z(n):=1/4 ⌊ n/2 ⌋ ⌊(n-1)/2⌋ ⌊ (n-2)/2 ⌋ ⌊ (n-3)/2 ⌋ and provided drawings of Kn with exactly Z(n) crossings. Towards the end of the century, substantially different drawings of Kn with Z(n) crossings were found. These drawings are 2-page book drawings, that is, drawings where all the vertices are on a line l (the spine) and each edge is fully contained in one of the two half-planes (pages) defined by l. The 2-page crossing number of Kn, denoted by ν2(Kn), is the minimum number of crossings determined by a 2-page book drawing of Kn. Since CRG(Kn) ≤ ν2(Kn) and ν2(Kn) ≤ Z(n), a natural step towards Hill's Conjecture is the weaker conjecture ν2(Kn) = Z(n), that was popularized by Vrt'o. In this paper we develop a novel and innovative technique to investigate crossings in drawings of Kn, and use it to prove that ν2(Kn) = 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 Kn. We also introduce the concept of ≤≤k-edges as a useful generalization of ≤k-edges. Finally, we extend a powerful theorem that expresses the number of crossings in a rectilinear drawing of Kn in terms of its number of k-edges to the topological setting.