We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Intersection graphs of L-shapes and segments in the plane.

Felsner, S. and Knauer, K. and Mertzios, G.B. and 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. Berlin, Heidelberg: Springer, pp. 299-310. Lecture notes in computer science. (8635).


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.

Item Type:Book chapter
Keywords:Intersection graphs, Segment graphs, Co-planar graphs, k-bend VPG-graphs, Planar 3-trees.
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:The final publication is available at Springer via
Date accepted:No date available
Date deposited:17 September 2014
Date of first online publication:2014
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar