S. Felsner
Intersection Graphs of L-Shapes and Segments in the Plane
Felsner, S.; Knauer, K.; Mertzios, G.B.; Ueckerdt, T.
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
Accepted Journal Article
(378 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by-nc-nd/4.0/
Copyright 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/
You might also like
Graphs with minimum fractional domatic number
(2023)
Journal Article
Approximate and Randomized algorithms for Computing a Second Hamiltonian Cycle
(2023)
Journal Article
Sliding into the Future: Investigating Sliding Windows in Temporal Graphs
(2023)
Conference Proceeding
Fast parameterized preprocessing for polynomial-time solvable graph problems
(2023)
Journal Article
The complexity of computing optimum labelings for temporal connectivity
(2022)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search