We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science


Publication details for Dr George Mertzios

Felsner, S., Knauer, K., Mertzios, G.B. & Ueckerdt, T. (2016). Intersection Graphs of L-Shapes and Segments in the Plane. Discrete Applied Mathematics 206: 48-55.

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: Full-size image (25 K), Full-size image (25 K),Full-size image (25 K) and Full-size image (25 K). 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 Full-size image (25 K), an Full-size image (25 K) or Full-size image (25 K), a k-bend path, or a segment, then this graph is called an {Full-size image (25 K)}-graph, {Full-size image (25 K),Full-size image (25 K)}-graph, Bk-VPG-graph or SEG-graph, respectively. Motivated by a theorem of Middendorf and Pfeiffer (1992), stating that every {Full-size image (25 K),Full-size image (25 K)}-graph is a SEG-graph, we investigate several known subclasses of SEG-graphs and show that they are {Full-size image (25 K)}-graphs, or Bk-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 {Full-size image (25 K)}-graphs. Furthermore we show that complements of planar graphs are B17-VPG-graphs and complements of full subdivisions are B2-VPG-graphs. Here a full subdivision is a graph in which each edge is subdivided at least once.