Intersection Graphs of L-Shapes and Segments in the Plane

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

doi:10.1007/978-3-662-44465-8_26

Intersection Graphs of L-Shapes and Segments in the Plane

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

Authors

S. Felsner

K. Knauer

Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor

T. Ueckerdt

Contributors

Erzsébet Csuhaj-Varjú
Editor

Martin Dietzfelbinger
Editor

Zoltán Ésik
Editor

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.
Related Public URLs	http://link.springer.com/chapter/10.1007/978-3-662-44465-8_26