TY - GEN
T1 - The 2-page crossing number of K n
AU - Ábrego, Bernardo M.
AU - Aichholzer, Oswin
AU - Fernández-Merchant, Silvia
AU - Ramos, Pedro
AU - Salazar, Gelasio
PY - 2012
Y1 - 2012
N2 - 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.
AB - 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.
KW - Complete graph
KW - Crossing number
KW - Topological drawing
KW - Discrete and Computational Geometry
UR - http://www.scopus.com/inward/record.url?scp=84863928388&partnerID=8YFLogxK
U2 - 10.1145/2261250.2261310
DO - 10.1145/2261250.2261310
M3 - Conference paper
AN - SCOPUS:84863928388
SN - 9781450312998
T3 - Proceedings of the Annual Symposium on Computational Geometry
SP - 397
EP - 403
BT - Proceedings of the 28th Annual Symposuim on Computational Geometry, SCG 2012
T2 - 28th Annual Symposuim on Computational Geometry
Y2 - 17 June 2012 through 20 June 2012
ER -