Geometric Thickness of Multigraphs is $$\exists \mathbb {R}$$-Complete
Henry Förster, Philipp Kindermann, Tillmann Miltzow, Irene Parada, Soeren Terziadis, Birgit Vogtenhuber · Algorithmica · 2025
Abstract We say that a (multi)graph $$ \user2{G} = (\user2{V},\user2{E}) $$ has geometric thickness t if there exists a straight-line drawing $$ \user2{\varphi }:\user2{V} \to \mathbb{R}^{{\mathbf{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 . This problem was shown to be NP-hard for $$ \user2{t} = \mathbf{2} $$ (Durocher et al. Comput Geom 56:1–18, 2016. https://doi.org/10.1016/j.comgeo.2016.03.003 ). In this paper, we settle the computational complexity of Geometric Thickness by showing that it is $$\exists \mathbb {R}$$ -complete already for thickness 30 . Moreover, our reduction shows that the problem is $$\exists \mathbb {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 $$\exists \mathbb {R}$$ -complete.