Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00411
On the Complexity of the Planar Slope Number Problem
Vol. 21, no. 2, pp. 183-193, 2017. Concise paper.
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.
Submitted: October 2016.
Reviewed: December 2016.
Revised: January 2017.
Accepted: January 2017.
Final: January 2017.
Published: January 2017.
Communicated by Giuseppe Liotta
article (PDF)
BibTeX