An L-shape is the union of a horizontal and a vertical segment with a common endpoint. These come in four rotations: Full-size image (25 K), Full-size image (25 K),Full-size image (25 K) and Full-size image (25 K). 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 Full-size image (25 K), an Full-size image (25 K) or Full-size image (25 K), a k-bend path, or a segment, then this graph is called an {Full-size image (25 K)}-graph, {Full-size image (25 K),Full-size image (25 K)}-graph, Bk-VPG-graph or SEG-graph, respectively. Motivated by a theorem of Middendorf and Pfeiffer (1992), stating that every {Full-size image (25 K),Full-size image (25 K)}-graph is a SEG-graph, we investigate several known subclasses of SEG-graphs and show that they are {Full-size image (25 K)}-graphs, or Bk-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 {Full-size image (25 K)}-graphs. Furthermore we show that complements of planar graphs are B17-VPG-graphs and complements of full subdivisions are B2-VPG-graphs. Here a full subdivision is a graph in which each edge is subdivided at least once.
展开▼
