Intersection Graphs of L-Shapes and Segments in the Plane

Felsner, S.; Knauer, K.; Mertzios, G.B.; Ueckerdt, T.

Abstract

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.

Citation

Felsner, S., Knauer, K., Mertzios, G., & Ueckerdt, T. (2014). Intersection Graphs of L-Shapes and Segments in the Plane. In E. Csuhaj-Varjú, M. Dietzfelbinger, & Z. Ésik (Eds.), Mathematical foundations of computer science 2014 : 39th international symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, part II (299-310). Springer Verlag. https://doi.org/10.1007/978-3-662-44465-8_26

• Publication Date: 2014
• Deposit Date: Sep 8, 2014
• Publicly Available Date: Sep 17, 2014
• Publisher: Springer Verlag
• Pages: 299-310
• Series Title: Lecture notes in computer science
• Book Title: Mathematical foundations of computer science 2014 : 39th international symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, part II.
• ISBN: 9783662444641
• DOI: https://doi.org/10.1007/978-3-662-44465-8_26
• Keywords: Intersection graphs, Segment graphs, Co-planar graphs, k-bend VPG-graphs, Planar 3-trees.
• Public URL: https://durham-repository.worktribe.com/output/1648218
• Related Public URLs: http://link.springer.com/chapter/10.1007/978-3-662-44465-8_26