2024/06/25 by Jean Cardinal, Cardinal, Jean
Computer Science · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Data Management and Algorithms
paper · pdf · doi:10.48550/arxiv.2406.17504
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 ℝ3 so that vw is an edge in E if and only if ℓ(v) and ℓ(w) intersect. A partially ordered set (X,\prec) 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\prec 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.