Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418503 | Discrete Applied Mathematics | 2016 | 8 Pages |
An L-shape is the union of a horizontal and a vertical segment with a common endpoint. These come in four rotations: , ,, and . A kk-bend path is a simple path in the plane, whose direction changes kk times from horizontal to vertical. If a graph admits an intersection representation in which every vertex is represented by an , an or , a kk-bend path, or a segment, then this graph is called an {}-graph, {,}-graph, BkBk-VPGVPG-graph or SEGSEG-graph, respectively. Motivated by a theorem of Middendorf and Pfeiffer (1992), stating that every {,}-graph is a SEGSEG-graph, we investigate several known subclasses of SEGSEG-graphs and show that they are {}-graphs, or BkBk-VPGVPG-graphs for some small constant kk. We show that all planar 3-trees, all line graphs of planar graphs, and all full subdivisions of planar graphs are {}-graphs. Furthermore we show that complements of planar graphs are B17B17-VPGVPG-graphs and complements of full subdivisions are B2B2-VPGVPG-graphs. Here a full subdivision is a graph in which each edge is subdivided at least once.