Abstract(s) :
(Anglais) 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.