论文标题
完整图的斜率约束图的NP完整性
NP-completeness of slope-constrained drawing of complete graphs
论文作者
论文摘要
我们证明了以下问题的NP完整性。给定$ n $斜率的$ s $ s $和一个整数$ k \ geq 1 $，是否可以在飞机上仅使用$ s $的坡度在飞机上的$ k $顶点上绘制完整的图形？同等地，是否存在$ k $ k $点的$ k $的一般位置，以使每个细分市场之间的斜率在$ s $中为$ s $？然后，当$ n \ leq 2k-c $（以R.E.贾米森。对于$ n = k $，Wade and Chu提出了$ \ Mathcal {O}（n^4）$中的算法。对于这种情况，我们的算法是线性的，不依赖贾米森的猜想。
We prove the NP-completeness of the following problem. Given a set $S$ of $n$ slopes and an integer $k\geq 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 algorithm for this question when $n\leq 2k-c$, conditional on a conjecture of R.E. Jamison. For $n=k$, an algorithm in $\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.
