{
  "id": "0906.0515",
  "version": "v1",
  "published": "2009-06-02T15:42:32.000Z",
  "updated": "2009-06-02T15:42:32.000Z",
  "title": "On the Order Dimension of Outerplanar Maps",
  "authors": [
    "Stefan Felsner",
    "Johan Nilsson"
  ],
  "comment": "Contains full details for the final section {Concluding remarks}",
  "categories": [
    "math.CO"
  ],
  "abstract": "Schnyder characterized planar graphs in terms of order dimension. Brightwell and Trotter proved that the dimension of the vertex-edge-face poset $\\Pvef{M}$ of a planar map $M$ is at most four. In this paper we investigate cases where $\\dim(\\Pvef{M}) \\leq 3$ and also where $\\dim(\\Qvf{M}) \\leq 3$; here $\\Qvf{M}$ denotes the vertex-face poset of $M$. We show: - If $M$ contains a $K_4$-subdivision, then $\\dim(\\Pvef{M}) = \\dim(\\Qvf{M}) = 4$. - If $M$ or the dual $M^*$ contains a $K_{2,3}$-subdivision, then $\\dim(\\Pvef{M}) = 4$. Hence, a map $M$ with $\\dim(\\Pvef{M}) \\leq 3$ must be outerplanar and have an outerplanar dual. We concentrate on the simplest class of such maps and prove that within this class $\\dim(\\Pvef{M}) \\leq 3$ is equivalent to the existence of a certain oriented coloring of edges. This condition is easily checked and can be turned into a linear time algorithm returning a 3-realizer. Additionally, we prove that if $M$ is 2-connected and $M$ and $M^*$ are outerplanar, then $\\dim(\\Qvf{M}) \\leq 3$. There are, however, outerplanar maps with $\\dim(\\Qvf{M}) = 4$. We construct the first such example.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2009-06-02T15:42:32.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C10",
      "06A07",
      "68R10"
    ],
    "keywords": [
      "outerplanar maps",
      "order dimension",
      "schnyder characterized planar graphs",
      "vertex-edge-face poset",
      "vertex-face poset"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0906.0515F"
    }
  }
}