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, Los Angeles, CA, USA , pp. 447-459 (Official URL:

Full text not available from this repository.


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
ID Code:1511

Repository Staff Only: item control page


Alt, H., Knauer, C., Rote, G., Whitesides, S.: On the complexity of the linkage reconfiguration problem. In: Pach, J. (ed.) Towards a Theory of Geometric Graphs, vol. 342, Contemporary Mathematics, pp. 1–14. AMS, Providence (2004)

Ballinger, B., Charlton, D., Demaine, E.D., Demaine, M.L., Iacono, J., Liu, C.-H., Poon, S.-H.: Minimal locked trees. In: Dehne, F., Gavrilova, M., Sack, J.-R., Tóth, C.D. (eds.) WADS 2009. LNCS, vol. 5664, pp. 61–73. Springer, Heidelberg (2009)

Biedl, T., Kant, G.: A better heuristic for orthogonal graph drawings. Comput. Geom. 9(3), 159–180 (1998)

Bhatt, S.N., Cosmadakis, S.S.: The complexity of minimizing wire lengths in VLSI layouts. Inform. Process. Lett. 25(4), 263–267 (1987)

Breu, H., Kirkpatrick, D.G.: On the complexity of recognizing intersection and touching graphs of discs. In: Brandenburd, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 88–98. Spinger, Heidelberg (1996)

Breu, H., Kirkpatrick, D.G.: Unit disk graph recognition is NP-hard. Comput. Geom. 9, 3–24 (1998)

Cabello, S., Demaine, E.D., Rote, G.: Planar embeddings of graphs with specified edge lengths. J. Graph Alg. Appl. 11(1), 259–276 (2007)

Cheong, J.-S., van der Stappen, A.F., Goldberg, K., Overmars, M.H., Rimon, E.: Immobilizing hinged polygons. Int. J. Comput. Geom. Appl. 17(1), 45–70 (2007)

Connelly, R., Demaine, E.D.: Geometry and topology of polygonal linkages. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, ch. 9, pp. 197–218. CRC, Boca Raton (2004)

Connelly, R., Demaine, E.D., Rote, G.: Straightening polygonal arcs and convexifying polygonal cycles. Discrete Comput. Geom. 30(2), 205–239 (2003)

Connelly, R., Demaine, E.D., Demaine, M.L., Fekete, S.P., Langerman, S., Mitchell, J.S.B., Ribó, A., Rote, G.: Locked and unlocked chains of planar shapes. Discrete Comput. Geom. 44(2), 439–462 (2010)

Demaine, E.D., Eppstein, D., Erickson, J., Hart, G.W., O’Rourke, J.: Vertex-unfoldings of simplicial manifolds. In: 18th Sympos. on Comput. Geom., pp. 237–243. ACM Press, New York (2002)

Di Battista, G., Vismara, L.: Angles of planar triangular graphs. SIAM J. Discrete Math. 9(3), 349–359 (1996)

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, Upper Saddle River (1999)

Eades, P., Whitesides, S.: The realization problem for Euclidean minimum spanning trees is NP-hard. Algorithmica 16(1), 60–82 (1996)

Eades, P., Wormald, N.C.: Fixed edge-length graph drawing is NP-hard. Discrete Appl. Math. 28, 111–134 (1990)

Fekete, S.P., Houle, M.E., Whitesides, S.: The wobbly logic engine: Proving hardness of non-rigid geometric graph representation problems. In: Di Battista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 272–283. Springer, Heidelberg (1997)

Gregori, A.: Unit-length embedding of binary trees on a square grid. Inform. Process. Lett. 31, 167–173 (1989)

Hliněný, P.: Touching graphs of unit balls. In: Di Battista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 350–358. Springer, Heidelberg (1997)


Hliněný, P., Kratochvíl, J.: Representing graphs by disks and balls (a survey of recognition-complexity results). Discrete Math. 229(1–3), 101–124 (2001)

Klemz, B., Nöllenburg, M., Prutkin, R.: Recognizing weighted disk contact graphs. In: Di Giacomo, E., Lubiw, A. (eds.) GD 2015. LNCS, vol. 9411, pp. 433–446. LNCS, Spinger, Heidelberg (2015)

Reif, J.H.: Complexity of the mover’s problem and generalizations. In: 20th FoCS, pp. 421–427. IEEE, New York (1979)

Schaefer, M.: Realizability of graphs and linkages. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 461–482. Springer, Heidelberg (2013)

Streinu, I.: Pseudo-triangulations, rigidity and motion planning. Discrete Comput. Geom. 34(4), 587–635 (2005)

Whitney, H.: Congruent graphs and the connectivity of graphs. Amer. J. Math. 54, 150–168 (1932)