On the Complexity of the Planar Slope Number Problem

Abstract

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.