Geometric Thickness of Multigraphs is $\exists \mathbb{R}$-complete

Henry Förster, Philipp Kindermann, Tillmann Miltzow +3

We say that a (multi)graph $G=(V,E)$ has geometric thickness $t$ if there exists a straight-line drawing $\phi :V\to {\mathbb{R}}^2$ and a $t$-coloring of its edges where no…