On the Complexity of the Planar Slope Number Problem
Udo Hoffmann · Journal of Graph Algorithms and Applications · 2017
The planar slope number of a planar graph $G$ is defined as the minimum number of slopes that is required for a crossing-free straight-line drawing of $G$. We show that determining the planar slope number is hard in the existential theory of the reals. We discuss consequences for drawings that minimize the planar slope number.