Flat-state connectivity of linkages under dihedral motions

Greg Aloupis, Erik D. Demaine, Vida Dujmović, Jeff Erickson, Stefan Langerman, Henk Meijer, Joseph O'Rourke, Mark Overmars, Michael Soss, Ileana Streinu, Godfried T. Toussaint

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We explore which classes of linkages have the property that each pair of their flat states - that is, their embeddings in ℝ2 without self-intersection - can be connected by a continuous dihedral motion that avoids self-intersection throughout. Dihedral motions preserve all angles between pairs of incident edges, which is most natural for protein models. Our positive results include proofs that open chains with nonacute angles are flat-state connected, as are closed orthogonal unit-length chains. Among our negative results is an example of an orthogonal graph linkage that is flat-state disconnected. Several additional results are obtained for other restrictedclasses of linkages. Many open problems are posed.

Original languageEnglish (US)
Title of host publicationAlgorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings
Number of pages12
StatePublished - 2002
Event13th Annual International Symposium on Algorithms and Computation, ISAAC 2002 - Vancouver, BC, Canada
Duration: Nov 21 2002Nov 23 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2518 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other13th Annual International Symposium on Algorithms and Computation, ISAAC 2002
CityVancouver, BC

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Flat-state connectivity of linkages under dihedral motions'. Together they form a unique fingerprint.

Cite this