{
  "id": "1405.1476",
  "version": "v2",
  "published": "2014-05-07T00:03:41.000Z",
  "updated": "2016-01-07T10:36:04.000Z",
  "title": "Intersection Graphs of L-Shapes and Segments in the Plane",
  "authors": [
    "Stefan Felsner",
    "Kolja Knauer",
    "George B. Mertzios",
    "Torsten Ueckerdt"
  ],
  "comment": "15 pages, 8 figures, (improved Thm. 4)",
  "categories": [
    "math.CO"
  ],
  "abstract": "An L-shape is the union of a horizontal and a vertical segment with a common endpoint. These come in four rotations: L, \\Gamma, LE{} and \\eeG. A $k$-bend path is a simple path in the plane, whose direction changes $k$ times from horizontal to vertical. If a graph admits an intersection representation in which every vertex is represented by an L, an L{} or \\Gamma, a $k$-bend path, or a segment, then this graph is called an $\\{L\\}$-graph, $\\{L,\\Gamma\\}$-graph, $B_k$-VPG-graph or SEG-graph, respectively. Motivated by a theorem of Middendorf and Pfeiffer [Discrete Mathematics, 108(1):365--372, 1992], stating that every $\\{L,\\Gamma\\}$-graph is a SEG-graph, we investigate several known subclasses of SEG-graphs and show that they are $\\{L\\}$-graphs, or $B_k$-VPG-graphs for some small constant $k$. We show that all planar $3$-trees, all line graphs of planar graphs, and all full subdivisions of planar graphs are $\\{L\\}$-graphs. Furthermore we show that all complements of planar graphs are $B_{17}$-VPG-graphs and all complements of full subdivisions are $B_2$-VPG-graphs. Here a full subdivision is a graph in which each edge is subdivided at least once.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-05-07T00:03:41.000Z",
      "abstract": "An L-shape is the union of a horizontal and a vertical segment with a common endpoint. These come in four rotations: L, \\Gamma, LE{} and \\eeG. A $k$-bend path is a simple path in the plane, whose direction changes $k$ times from horizontal to vertical. If a graph admits an intersection representation in which every vertex is represented by an L, an L{} or \\Gamma, a $k$-bend path, or a segment, then this graph is called an $\\{L\\}$-graph, $\\{L,\\Gamma\\}$-graph, $B_k$-VPG-graph or SEG-graph, respectively. Motivated by a theorem of Middendorf and Pfeiffer [Discrete Mathematics, 108(1):365--372, 1992], stating that every $\\{L,\\Gamma\\}$-graph is a SEG-graph, we investigate several known subclasses of SEG-graphs and show that they are $\\{L\\}$-graphs, or $B_k$-VPG-graphs for some small constant $k$. We show that all planar $3$-trees, all line graphs of planar graphs, and all full subdivisions of planar graphs are $\\{L\\}$-graphs. Furthermore we show that all complements of planar graphs are $B_{19}$-VPG-graphs and all complements of full subdivisions are $B_2$-VPG-graphs. Here a full subdivision is a graph in which each edge is subdivided at least once.",
      "comment": "14 pages, 8 figures",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2016-01-07T10:36:04.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "intersection graphs",
      "planar graphs",
      "full subdivision",
      "bend path",
      "common endpoint"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1405.1476F"
    }
  }
}