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
OA 2019_eJourCombinatorics_Jelinek.pdf 533.70 KB

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
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)
Access Level
OA Open Access
Date Uploaded
2019-08-05
MD5 Checksum
20fc366fc6683ef0b074a019b73a663a


Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 1808.04148

Search this title in

Google Scholar