The 2-page crossing number of K n Conference Paper uri icon

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%27s Conjecture is the weaker conjecture ν 2(K n) = Z(n), that was popularized by Vrt%27o. 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. Copyright © 2012 ACM.
  • 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. Copyright © 2012 ACM.

publication date

  • 2012-01-01