{
  "id": "1210.2918",
  "version": "v1",
  "published": "2012-10-10T13:48:13.000Z",
  "updated": "2012-10-10T13:48:13.000Z",
  "title": "Book drawings of complete bipartite graphs",
  "authors": [
    "Etienne de Klerk",
    "Dmitrii V. Pasechnik",
    "Gelasio Salazar"
  ],
  "comment": "22 pages, 5 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "A \"book\" with k pages consists of a straight line (the \"spine\") and k half-planes (the \"pages\"), such that the boundary of each page is the spine. If a graph is drawn on a book with k pages in such a way that the vertices lie on the spine, and each edge is contained in a page, the result is a k-page book drawing (or simply a k-page drawing). The pagenumber of a graph G is the minimum k such that G admits a k-page embedding (that is, a k-page drawing with no edge crossings). The k-page crossing number nu_k(G) of G is the minimum number of crossings in a k-page drawing of G. We investigate the pagenumbers and k-page crossing numbers of complete bipartite graphs. We find the exact pagenumbers of several complete bipartite graphs, and use these pagenumbers to find the exact k-page crossing number of K_{k+1,n} for 3<=k<=6. We also prove the general asymptotic estimate lim_{k->oo} lim_{n->oo} nu_k(K_{k+1,n})/(2n^2/k^2)=1. Finally, we give general upper bounds for nu_k(K_{m,n}), and relate these bounds to the k-planar crossing numbers of K_{m,n} and K_n.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-10-10T13:48:13.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "complete bipartite graphs",
      "book drawing",
      "k-page drawing",
      "pagenumber",
      "general upper bounds"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 22,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1210.2918D"
    }
  }
}