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
|
Journal Supporters
|