Intersection Graphs of Rays and Grounded Segments

J. Cardinal, S. Felsner, T. Miltzow, C. Tompkins, and B. Vogtenhuber

Abstract:

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.

Reference: J. Cardinal, S. Felsner, T. Miltzow, C. Tompkins, and B. Vogtenhuber. Intersection graphs of rays and grounded segments. In H. L. Bodlaender and G. J. Woeginger, editors, Graph-Theoretic Concepts in Computer Science (WG 2017), pages 153-166, Cham, 2017. Springer International Publishing. Revised Selected Papers.