On grounded L-graphs and their relatives

V. Jelínek, M. Töpfer, Electronic Journal of Combinatorics 26 (2019) P3.17.

Download
OA 533.70 KB
Journal Article | Published | English
Author
;
Department
Abstract
We consider the graph class Grounded-L corresponding to graphs that admit an intersection representation by L-shaped curves, where additionally the topmost points of each curve are assumed to belong to a common horizontal line. We prove that Grounded-L graphs admit an equivalent characterisation in terms of vertex ordering with forbidden patterns. We also compare this class to related intersection classes, such as the grounded segment graphs, the monotone L-graphs (a.k.a. max point-tolerance graphs), or the outer-1-string graphs. We give constructions showing that these classes are all distinct and satisfy only trivial or previously known inclusions.
Publishing Year
Date Published
2019-07-19
Journal Title
Electronic Journal of Combinatorics
Volume
26
Issue
3
Article Number
P3.17
eISSN
IST-REx-ID

Cite this

Jelínek V, Töpfer M. On grounded L-graphs and their relatives. Electronic Journal of Combinatorics. 2019;26(3):P3.17.
Jelínek, V., & Töpfer, M. (2019). On grounded L-graphs and their relatives. Electronic Journal of Combinatorics, 26(3), P3.17.
Jelínek, Vít, and Martin Töpfer. “On Grounded L-Graphs and Their Relatives.” Electronic Journal of Combinatorics 26, no. 3 (2019): P3.17.
V. Jelínek and M. Töpfer, “On grounded L-graphs and their relatives,” Electronic Journal of Combinatorics, vol. 26, no. 3, p. P3.17, 2019.
Jelínek V, Töpfer M. 2019. On grounded L-graphs and their relatives. Electronic Journal of Combinatorics. 26(3), P3.17.
Jelínek, Vít, and Martin Töpfer. “On Grounded L-Graphs and Their Relatives.” Electronic Journal of Combinatorics, vol. 26, no. 3, Electronic Journal of Combinatorics, 2019, p. P3.17.
All files available under the following license(s):
Creative Commons License:
CC-BYCreative Commons Attribution 4.0 International Public License (CC-BY 4.0)
Main File(s)
Access Level
OA Open Access
Last Uploaded
2019-08-05T06:46:55Z


Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1808.04148

Search this title in

Google Scholar