## Helmut Alt, Christian Knauer, Günter Rote, and Sue Whitesides:

# 1. The complexity of (un)folding

*In: Proceedings of the Nineteenth Annual Symposium on Computational
Geometry, San Diego, June 8–10, 2003. Association for
Computing Machinery, 2003, pp. 164–170. *doi:10.1145/777792.777818
# 2. On the complexity of the linkage reconfiguration problem

*In: "Towards a Theory of Geometric Graphs". Editor: János
Pach,
American Mathematical Society, 2004, Contemporary Mathematics,
Vol. 342,
pp. 1–13.
*
### Abstract

We consider the problem of reconguring a linkage of rigid straight
segments
from a given start to a given target position with a continuous
nonintersecting motion. The problem is nontrivial even for trees in two
dimensions since it is known that not all congurations can be
recongured to
a straight position. We show that deciding recongurability for trees in
two
dimensions and for chains in three dimensions is PSPACE-complete.
Last update: January 12, 2007.