我们确切地解决了图形实现,图形刚性和图形全局刚性的复杂性,应用于三种类型的图形:“全局非交叉”图形,这避免了所有配置的交叉;匹配杆图形,具有单位长度边缘并且只考虑非交叉配置;以及具有单位边缘长度的无限制图形(允许交叉)(或全局刚性情况下,边缘长度在{1,2}中)。 我们表明,所有九个问题都是完整的类∃R,由真实世界存在理论或其补充∀R定义;特别是,每个问题都是(co)NP-hard。 这九个结果之一 - 单位距离图的实现是∃R-complete - 以前由Schaefer(2013)显示,但其他八个是新的。 我们加强了以前的几项成果。 火柴杆图实现已知是NP-hard(Eades&Wormald 1990,或Cabello等人)。 2007年),但它在NP的成员资格仍然开放;我们表明它是完整的(可能)更大的类∃R。 已知在{1,2}中具有边缘长度的图形的全局刚性是coNP-hard(Saxe 1979);我们显示它是∀R-complete。 论文的大部分内容都致力于证明肯普的普遍性定理的类似物 - 非正式地,“有一个链接来签署你的名字” - 用于全球非交叉联系。 特别是,我们表明任何多项式曲线 φ(x,y)=0 都可以通过非交叉联动来追踪,从2004年开始解决一个开放的问题。 更一般地说,我们表明,平面中可能通过非交叉联动所追踪的区域恰恰是紧凑的半代数区域(加上整个平面的琐碎情况)。 因此,不因限制非交叉联系而失去任何绘图能力。 我们在火柴杆连接和单位距离连接方面也证明了类似的结果。