Skip to main content

Research Repository

Advanced Search

Intersection Graphs of L-Shapes and Segments in the Plane

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

Intersection Graphs of L-Shapes and Segments in the Plane Thumbnail


Authors

S. Felsner

K. Knauer

T. Ueckerdt



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.

Citation

Felsner, S., Knauer, K., Mertzios, G., & Ueckerdt, T. (2016). Intersection Graphs of L-Shapes and Segments in the Plane. Discrete Applied Mathematics, 206, 48-55. https://doi.org/10.1016/j.dam.2016.01.028

Journal Article Type Article
Acceptance Date Jan 22, 2016
Online Publication Date Feb 19, 2016
Publication Date Jun 1, 2016
Deposit Date Feb 12, 2016
Publicly Available Date Mar 29, 2024
Journal Discrete Applied Mathematics
Print ISSN 0166-218X
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 206
Pages 48-55
DOI https://doi.org/10.1016/j.dam.2016.01.028

Files





You might also like



Downloadable Citations