NP-completeness of slope-constrained drawing of complete graphs

preprint2020arXivOpen access

Abstract

We prove the NP-completeness of the following problem. Given a set SS of nn slopes and an integer k≥1k\geq 1, is it possible to draw a complete graph on kk vertices in the plane using only slopes from SS? Equivalently, does there exist a set KK of kk points in general position such that the slope of every segment between two points of KK is in SS? We then present a polynomial algorithm for this question when n≤2k−cn\leq 2k-c, conditional on a conjecture of R.E. Jamison. For n=kn=k, an algorithm in O(n4)\mathcal{O}(n^4) was proposed by Wade and Chu. For this case, our algorithm is linear and does not rely on Jamison's conjecture.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.