Veröffentlichung

Titel:

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

AutorInnen:

Clinton Bowen
Stephane Durocher
Maarten Löffler
Anika Rounds
André Schulz
Csaba D. Tóth

Kategorie:

Konferenzbandbeiträge

erschienen in:

Graph Drawing and Network Visualization - 23rd International Symposium, GD 2015, Los Angeles, CA, USA, September 24-26, 2015, Revised Selected Papers, pp. 447-459

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.

Download:

Springer

BibTeX-Eintrag:

@inproceedings{BDLRST15, author = {Clinton Bowen and Stephane Durocher and Maarten L{\"{o}}ffler and Anika Rounds and Andr{\'{e}} Schulz and Csaba D. T{\'{o}}th}, editor = {Emilio Di Giacomo and Anna Lubiw}, title = {Realization of Simply Connected Polygonal Linkages and Recognition of Unit Disk Contact Trees}, booktitle = {Graph Drawing and Network Visualization - 23rd International Symposium, {GD} 2015, Los Angeles, CA, USA, September 24-26, 2015, Revised Selected Papers}, series = {Lecture Notes in Computer Science}, volume = {9411}, pages = {447--459}, publisher = {Springer}, year = {2015}, url = {http://dx.doi.org/10.1007/978-3-319-27261-0_37}, doi = {10.1007/978-3-319-27261-0_37} }