Publication details for Dr George MertziosFelsner, S. Knauer, K., Mertzios, G.B. & Ueckerdt, T. (2014). Intersection Graphs of L-Shapes and Segments in the Plane. In Mathematical Foundations of Computer Science 2014: 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II. Csuhaj-Varjú, Erzsébet, Dietzfelbinger, Martin & Ésik, Zoltán Berlin, Heidelberg: Springer. 8635: 299-310.
- Publication type: Chapter in book
- ISSN/ISBN: 0302-9743 (print), 1611-3349 (electronic), 978-3-662-44464-1 (print), 978-3-662-44465-8 (electronic)
- DOI: 10.1007/978-3-662-44465-8_26
- Keywords: Intersection graphs, Segment graphs, Co-planar graphs, k-bend VPG-graphs, Planar 3-trees.
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
- View in another repository - may include full text
Author(s) from Durham
An L-shape is the union of a horizontal and a vertical segment with a common endpoint. These come in four rotations: ⌊,⌈,⌋ and ⌉. 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 ⌊, an ⌊ or ⌈, a k-bend path, or a segment, then this graph is called an ⌊-graph, ⌊,⌈-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 ⌊,⌈-graph is a SEG-graph, we investigate several known subclasses of SEG-graphs and show that they are ⌊-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 ⌊-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.