The 2-page crossing number of K n

Bernardo M. Ábrego*, Oswin Aichholzer, Silvia Fernández-Merchant, Pedro Ramos, Gelasio Salazar

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review


Around 1958, Hill conjectured that the crossing number cr(K n) of the complete graph K n is (equation presented) and provided drawings of K n with exactly Z(n) crossings. 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 ν 2 (K n), is the minimum number of crossings determined by a 2-page book drawing of K n. Since cr(K n) ≤ ν 2(K n) and ν 2(K n) ≤ Z(n), a natural step towards Hill's Conjecture is the weaker conjecture ν 2(K n) = Z(n), that was popularized by Vrt'o. In this paper we develop a novel and innovative technique to investigate crossings in drawings of K n, and use it to prove that ν 2(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. Finally, we 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.

Original languageEnglish
Title of host publicationProceedings of the 28th Annual Symposuim on Computational Geometry, SCG 2012
Number of pages7
Publication statusPublished - 2012
Event28th Annual Symposuim on Computational Geometry: SCG 2012 - Chapel Hill, United States
Duration: 17 Jun 201220 Jun 2012

Publication series

NameProceedings of the Annual Symposium on Computational Geometry


Conference28th Annual Symposuim on Computational Geometry
Country/TerritoryUnited States
CityChapel Hill


  • Complete graph
  • Crossing number
  • Topological drawing

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics


Dive into the research topics of 'The 2-page crossing number of K n'. Together they form a unique fingerprint.

Cite this