We consider the graph classes Grounded-L and Grounded-{L,⅃} corresponding to graphs that admit an intersection representation by L-shaped curves (or L-shaped and ⅃-shaped curves, respectively), 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 these classes 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.
@article{10_37236_8096,
author = {V{\'\i}t Jel{\'\i}nek and Martin T\"opfer},
title = {On grounded \(\llcorner\)-graphs and their relatives},
journal = {The electronic journal of combinatorics},
year = {2019},
volume = {26},
number = {3},
doi = {10.37236/8096},
zbl = {1441.05164},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8096/}
}
TY - JOUR
AU - Vít Jelínek
AU - Martin Töpfer
TI - On grounded \(\llcorner\)-graphs and their relatives
JO - The electronic journal of combinatorics
PY - 2019
VL - 26
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/8096/
DO - 10.37236/8096
ID - 10_37236_8096
ER -
%0 Journal Article
%A Vít Jelínek
%A Martin Töpfer
%T On grounded \(\llcorner\)-graphs and their relatives
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/8096/
%R 10.37236/8096
%F 10_37236_8096
Vít Jelínek; Martin Töpfer. On grounded \(\llcorner\)-graphs and their relatives. The electronic journal of combinatorics, Tome 26 (2019) no. 3. doi: 10.37236/8096
