{
  "id": "1009.4736",
  "version": "v2",
  "published": "2010-09-23T23:07:53.000Z",
  "updated": "2011-03-29T01:44:44.000Z",
  "title": "Point sets that minimize $(\\le k)$-edges, 3-decomposable drawings, and the rectilinear crossing number of $K_{30}$",
  "authors": [
    "M. Cetina",
    "C. Hernández-Vélez",
    "J. Leaños",
    "C. Villalobos"
  ],
  "comment": "14 pages",
  "doi": "10.1016/j.disc.2011.03.030",
  "categories": [
    "math.CO"
  ],
  "abstract": "There are two properties shared by all known crossing-minimizing geometric drawings of $K_n$, for $n$ a multiple of 3. First, the underlying $n$-point set of these drawings has exactly $3\\binom{k+2}{2}$ $(\\le k)$-edges, for all $0\\le k < n/3$. Second, all such drawings have the $n$ points divided into three groups of equal size; this last property is captured under the concept of 3-decomposability. In this paper we show that these properties are tightly related: every $n$-point set with exactly $3\\binom{k+2}{2}$ $(\\le k)$-edges for all $0\\le k < n/3$, is 3-decomposable. As an application, we prove that the rectilinear crossing number of $K_{30}$ is 9726.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2011-03-29T01:44:44.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "rectilinear crossing number",
      "point set",
      "crossing-minimizing geometric drawings",
      "application"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1009.4736C"
    }
  }
}