Geometric Thickness of Multigraphs is \(\exists \mathbb {R}\) -Complete

We say that a (multi)graph \(G = (V,E)\) has geometric thickness t if there exists a straight-line drawing \(\varphi : V \rightarrow \mathbb {R}^2\) and a t-coloring of its edges where no two edges sharing a point in their relative interior have the same color. The Geometric Thickness problem asks whether a given multigraph has geometric thickness at most t. In this paper, we settle the computational complexity of Geometric Thickness by showing that it is \(\exists \mathbb {R}\) -complete already for thickness \(57\) . Moreover, our reduction shows that the problem is \(\exists \mathbb {R}\) -complete for \(8280 \) -planar graphs, where a graph is k-planar if it admits a topological drawing with at most k crossings per edge. In this paper we answer previous questions on geometric thickness and on other related problems, in particular that simultaneous graph embeddings of \(58\) edge-disjoint graphs and pseudo-segment stretchability with chromatic number  \(57\) are \(\exists \mathbb {R}\) -complete.