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

Bowen, Clinton and Durocher, Stephane and Löffler, Maarten and Rounds, Anika and Schulz, André and Tóth, Csaba D. (2015) Realization of Simply Connected Polygonal Linkages and Recognition of Unit Disk Contact Trees. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015 , pp. 447-459(Official URL: http://dx.doi.org/10.1007/978-3-319-27261-0_37).

Full text not available from this repository.

Abstract

We wish to decide whether a simply connected flexible polygonal structure can be realized in Euclidean space. Two models are considered: polygonal linkages (body-and-joint framework) 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 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.

Item Type: Conference Paper
Classifications: P Styles > P.999 Others
Z Theory > Z.250 Geometry
Z Theory > Z.500 Representations
Z Theory > Z.750 Topology
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 04 May 2016 15:51
Last Modified: 04 May 2016 15:51
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1511

Actions (login required)

View Item View Item