The 2-page crossing number of K n

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

*Korrespondierende/r Autor/-in für diese Arbeit

Publikation: Beitrag in Buch/Bericht/KonferenzbandBeitrag in einem KonferenzbandBegutachtung

Abstract

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.

Originalspracheenglisch
TitelProceedings of the 28th Annual Symposuim on Computational Geometry, SCG 2012
Seiten397-403
Seitenumfang7
DOIs
PublikationsstatusVeröffentlicht - 2012
Veranstaltung28th Annual Symposuim on Computational Geometry: SCG 2012 - Chapel Hill, USA / Vereinigte Staaten
Dauer: 17 Juni 201220 Juni 2012

Publikationsreihe

NameProceedings of the Annual Symposium on Computational Geometry

Konferenz

Konferenz28th Annual Symposuim on Computational Geometry
Land/GebietUSA / Vereinigte Staaten
OrtChapel Hill
Zeitraum17/06/1220/06/12

Schlagwörter

  • Discrete and Computational Geometry

ASJC Scopus subject areas

  • Theoretische Informatik
  • Geometrie und Topologie
  • Computational Mathematics

Fingerprint

Untersuchen Sie die Forschungsthemen von „The 2-page crossing number of K n“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren