NP-completeness of slope-constrained drawing of complete graphs
share
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 also present a polynomial algorithm for this question when n≤ 2k-c, conditionally on a conjecture of R.E. Jamison. For n=k, an algorithm in O(n^4) was proposed by Wade and Chu. In this case, our algorithm is linear and does not rely on Jamison's conjecture.
READ FULL TEXT