J. Cardinal, S. Felsner, T. Miltzow, C. Tompkins, and B. Vogtenhuber
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 Jejcic. 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.