Geodesic
Intersection Graphs of Rays and Grounded Segments
Journal of Graph Algorithms and Applications, Tome 22 (2018) no. 2, pp. 273-295.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

We consider several classes of intersection graphs of line segments in the plane and prove new equality and separation results between those classes. In particular, we show that: intersection graphs of grounded segments and intersection graphs of downward rays form the same graph class, not every intersection graph of rays is an intersection graph of downward rays, and not every outer segment graph is an intersection graph of rays. The first result answers an open problem posed by Cabello and Jejčič. The third result confirms a conjecture by Cabello. We thereby completely elucidate the remaining open questions on the containment relations between these classes of segment graphs. We further characterize the complexity of the recognition problems for the classes of outer segment, grounded segment, and ray intersection graphs. We prove that these recognition problems are complete for the existential theory of the reals. This holds even if a 1-string realization is given as additional input.
DOI : 10.7155/jgaa.00470
Keywords: graph drawing, geometric intersection graphs, existential theory of the reals 
@article{JGAA_2018_22_2_a5,
     author = {Jean Cardinal and Stefan Felsner and Tillmann Miltzow and Casey Tompkins and Birgit Vogtenhuber},
     title = {Intersection {Graphs} of {Rays} and {Grounded} {Segments}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {273--295},
     publisher = {mathdoc},
     volume = {22},
     number = {2},
     year = {2018},
     doi = {10.7155/jgaa.00470},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00470/}
}
TY  - JOUR
AU  - Jean Cardinal
AU  - Stefan Felsner
AU  - Tillmann Miltzow
AU  - Casey Tompkins
AU  - Birgit Vogtenhuber
TI  - Intersection Graphs of Rays and Grounded Segments
JO  - Journal of Graph Algorithms and Applications
PY  - 2018
SP  - 273
EP  - 295
VL  - 22
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00470/
DO  - 10.7155/jgaa.00470
LA  - en
ID  - JGAA_2018_22_2_a5
ER  - 
%0 Journal Article
%A Jean Cardinal
%A Stefan Felsner
%A Tillmann Miltzow
%A Casey Tompkins
%A Birgit Vogtenhuber
%T Intersection Graphs of Rays and Grounded Segments
%J Journal of Graph Algorithms and Applications
%D 2018
%P 273-295
%V 22
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00470/
%R 10.7155/jgaa.00470
%G en
%F JGAA_2018_22_2_a5
Jean Cardinal; Stefan Felsner; Tillmann Miltzow; Casey Tompkins; Birgit Vogtenhuber. Intersection Graphs of Rays and Grounded Segments. Journal of Graph Algorithms and Applications, Tome 22 (2018) no. 2, pp. 273-295. doi : 10.7155/jgaa.00470. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00470/

Cité par Sources :