NP-COMPLETENESS OF SLOPE-CONSTRAINED DRAWING OF COMPLETE GRAPHS

We prove the NP-completeness of the following problem. Given a set S of n slopes and an integer k >= 1, is it possible to draw a complete graph on k vertices in the plane using only slopes from S ? Equivalently, does there exist a set K of k points in general position such that the slope of every segment between two points of K is in S ? We then present a polynomial-time algorithm for this question when n <= 2k - c, conditional on a conjecture of R.E. Jamison. For n = k, an algorithm in O(n(4)) was proposed by Wade and Chu. For this case, our algorithm is linear and does not rely on Jamison's conjecture.