Geometric Thickness of Multigraphs is existsR-complete

We say that a (multi)graph G=(V,E) has geometric thickness t if there exists a straight-line drawing φ:V→R2 and a t-coloring of its edges where no two edges sharing a point in their relative interior have the same color. The \textsc{Geometric Thickness} problem asks whether a given multigraph has geometric thickness at most t. This problem was shown to be NP-hard for t=2 [Durocher, Gethner, and Mondal, CG 2016]. In this paper, we settle the computational complexity of \textsc{Geometric Thickness} by showing that it is ∃R-complete already for thickness 30. Moreover, our reduction shows that the problem is ∃R-complete for 4392-planar graphs, where a graph is k-planar if it admits a topological drawing with at most k crossings per edge. In the course of our paper, we answer previous questions on geometric thickness and on other related problems, in particular that simultaneous graph embeddings of 31 edge-disjoint graphs and pseudo-segment stretchability with chromatic number 30 are ∃R-complete.