Cookies

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. (2016) 'Intersection graphs of L-shapes and segments in the plane.', Discrete applied mathematics., 206 . pp. 48-55.

Abstract

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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF
(369Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1016/j.dam.2016.01.028
Publisher statement:© 2016 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
Date accepted:22 January 2016
Date deposited:15 February 2016
Date of first online publication:19 February 2016
Date first made open access:19 February 2017

Save or Share this output

Export:
Export
Look up in GoogleScholar