{
  "id": "1806.04489",
  "version": "v1",
  "published": "2018-06-12T13:18:24.000Z",
  "updated": "2018-06-12T13:18:24.000Z",
  "title": "The queue-number of planar posets",
  "authors": [
    "Kolja Knauer",
    "Piotr Micek",
    "Torsten Ueckerdt"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Heath and Pemmaraju conjectured that the queue-number of a poset is bounded by its width and if the poset is planar then also by its height. We show that there are planar posets whose queue-number is larger than their height, refuting the second conjecture. On the other hand, we show that any poset of width $2$ has queue-number at most $2$, thus confirming the first conjecture in the first non-trivial case. Moreover, we improve the previously best known bounds and show that planar posets of width $w$ have queue-number at most $3w-2$ while any planar poset with $0$ and $1$ has queue-number at most its width.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-06-12T13:18:24.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C10",
      "06A07"
    ],
    "keywords": [
      "planar poset",
      "queue-number",
      "first non-trivial case",
      "second conjecture",
      "first conjecture"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}