Realization of Simply Connected Polygonal Linkages and Recognition of Unit Disk Contact Trees

Abstract

We consider two variants of the fundamental question of determining whether a simply connected flexible combinatorial structure can be realized in Euclidean space. Two models are considered: body-and-joint frameworks and contact graphs of unit disks in the plane. (1) We show that it is strongly NP-hard to decide whether a given polygonal linkage (body-and-bar framework) is realizable in the plane when the bodies are convex polygons and their contact graph is a tree; the problem is weakly NP-hard already for a chain of rectangles; but efficiently decidable for a chain of triangles hinged at distinct vertices. (2) We also show that it is strongly NP-hard to decide whether a given tree is the contact graph of interior-disjoint unit disks in the plane.