The Complexity of Intersection Graphs of Lines in Space and Circle Orders

Jean Cardinal

We consider the complexity of the recognition problem for two families of combinatorial structures. A graph $G=(V,E)$ is said to be an intersection graph of lines in space if every…