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

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 v∈ V can be mapped to a straight line (v) in R³ so that $vw$ is an edge in E if and only if (v) and (w) intersect. A partially ordered set (X,) is said to be a circle order, or a 2-space-time order, if every x∈ X can be mapped to a closed circular disk $C(x)$ so that y x if and only if $C(y)$ is contained in $C(x)$. We prove that the recognition problems for intersection graphs of lines and circle orders are both -complete, hence polynomial-time equivalent to deciding whether a system of polynomial equalities and inequalities has a solution over the reals. The second result addresses an open problem posed by Brightwell and Luczak.