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

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.


slides
keywords: Computational Geometry, Graph Drawing, Graphs Theory, UDG

Conference Proceedings (peer-reviewed)

André Schulz, Anika Rounds, Clinton Bowen, Csaba Tóth, Maarten Löffler, Stephane Durocher
Realization of Simply Connected Polygonal Linkages and Recognition of Unit Disk Contact Trees
Proc. 23rd International Symposium on Graph Drawing
LNCS 9411, 447–459, 2015
http://dx.doi.org/10.1007/978-3-319-27261-0_37

Workshop or Poster (weakly reviewed)

André Schulz, Anika Rounds, Clinton Bowen, Csaba Tóth, Maarten Löffler, Stephane Durocher
Realization of Simply Connected Polygonal Linkages
Abstracts 4th Young Researchers Forum, Computational Geometry Week 2015
12–13, 2015

back to list