On grounded L-graphs and their relatives
Jelínek V, Töpfer M. 2019. On grounded L-graphs and their relatives. Electronic Journal of Combinatorics. 26(3), P3.17.
Download
DOI
Journal Article
| Published
| English
Scopus indexed
Author
Jelínek, Vít;
Töpfer, MartinISTA
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
Publisher
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). doi:10.37236/8096
Jelínek, V., & Töpfer, M. (2019). On grounded L-graphs and their relatives. Electronic Journal of Combinatorics. Electronic Journal of Combinatorics. https://doi.org/10.37236/8096
Jelínek, Vít, and Martin Töpfer. “On Grounded L-Graphs and Their Relatives.” Electronic Journal of Combinatorics. Electronic Journal of Combinatorics, 2019. https://doi.org/10.37236/8096.
V. Jelínek and M. Töpfer, “On grounded L-graphs and their relatives,” Electronic Journal of Combinatorics, vol. 26, no. 3. Electronic Journal of Combinatorics, 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, P3.17, Electronic Journal of Combinatorics, 2019, doi:10.37236/8096.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
2019_eJourCombinatorics_Jelinek.pdf
533.70 KB
Access Level
Open Access
Date Uploaded
2019-08-05
MD5 Checksum
20fc366fc6683ef0b074a019b73a663a
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 1808.04148