{
  "id": "1206.5669",
  "version": "v1",
  "published": "2012-06-25T12:57:21.000Z",
  "updated": "2012-06-25T12:57:21.000Z",
  "title": "The 2-page crossing number of $K_n$",
  "authors": [
    "Bernardo M. Abrego",
    "Oswin Aichholzer",
    "Silvia Fernandez-Merchant",
    "Pedro Ramos",
    "Gelasio Salazar"
  ],
  "categories": [
    "math.CO",
    "cs.CG"
  ],
  "abstract": "Around 1958, Hill described how to draw the complete graph $K_n$ with [Z(n) :=1/4\\lfloor \\frac{n}{2}\\rfloor \\lfloor \\frac{n-1}{2}\\rfloor \\lfloor \\frac{n-2}{2}% \\rfloor \\lfloor \\frac{n-3}{2}\\rfloor] crossings, and conjectured that the crossing number $\\crg (K_{n})$ of $K_n$ is exactly Z(n). This is also known as Guy's conjecture as he later popularized it. Towards the end of the century, substantially different drawings of $K_{n}$ with Z(n) crossings were found. These drawings are \\emph{2-page book drawings}, that is, drawings where all the vertices are on a line $\\ell$ (the spine) and each edge is fully contained in one of the two half-planes (pages) defined by $\\ell$. The \\emph{2-page crossing number} of $K_{n} $, denoted by $\\nu_{2}(K_{n})$, is the minimum number of crossings determined by a 2-page book drawing of $K_{n}% $. Since $\\crg(K_{n}) \\le\\nu_{2}(K_{n})$ and $\\nu_{2}(K_{n}) \\le Z(n)$, a natural step towards Hill's Conjecture is the %(formally) weaker conjecture $\\nu_{2}(K_{n}) = Z(n)$, popularized by Vrt'o. %As far as we know, this natural %conjecture was first raised by Imrich Vrt'o in 2007. %Prior to this paper, results known for $\\nu_2(K_n)$ were basically %the same as for $\\crg (K_n)$. Here In this paper we develop a novel and innovative technique to investigate crossings in drawings of $K_{n}$, and use it to prove that $\\nu_{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 ${\\leq}{\\leq}k$-edges as a useful generalization of ${\\leq}k$-edges and extend a powerful theorem that expresses the number of crossings in a rectilinear drawing of $K_{n}$ in terms of its number of $(\\le k)$-edges to the topological setting.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-06-25T12:57:21.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "crossing number",
      "inherent geometric definition",
      "finite sets",
      "minimum number",
      "book drawing"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1206.5669A"
    }
  }
}