Paper by Erik D. Demaine

Reference:

Therese Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Steve Robbins, Ileana Streinu, Godfried Toussaint, and Sue Whitesides, “On Reconfiguring Tree Linkages: Trees can Lock”, in Proceedings of the 10th Canadian Conference on Computational Geometry (CCCG'98), Montréal, Québec, Canada, August 10–12, 1998.

BibTeX

@InProceedings{CCCG98c,
  AUTHOR        = {Therese Biedl and Erik Demaine and Martin Demaine
                   and Sylvain Lazard and Anna Lubiw and Joseph O'Rourke
                   and Steve Robbins and Ileana Streinu and Godfried Toussaint
                   and Sue Whitesides},
  TITLE         = {On Reconfiguring Tree Linkages: Trees can Lock},
  BOOKTITLE     = {Proceedings of the 10th Canadian Conference on Computational
                   Geometry (CCCG'98)},
  BOOKURL       = {http://cgm.cs.mcgill.ca/cccg98/},
  ADDRESS       = {Montr\'eal, Qu\'ebec, Canada},
  MONTH         = {August 10--12},
  YEAR          = 1998,

  LENGTH        = {11 pages; 20 minutes},
  PAPERS        = {LockedTreeDAM; LockedTreeTR},
  dblp          = {https://dblp.org/rec/conf/cccg/BiedlDDLLORSTW98},
  COMMENTS      = {This paper is also available from the
                   <A HREF="http://cgm.cs.mcgill.ca/cccg98/proceedings/">
                   electronic proceedings</A> as
                   <A HREF="http://cgm.cs.mcgill.ca/cccg98/proceedings/cccg98-biedl-reconfiguring.ps.gz">http://cgm.cs.mcgill.ca/cccg98/proceedings/cccg98-biedl-reconfiguring.ps.gz</A>, and as <A HREF="https://arXiv.org/abs/cs/9910024">arXiv:cs/9910024</A>.},
  WEBPAGES      = {linkage},
  unrefereed    = 1,
  ee            = {http://cgm.cs.mcgill.ca/cccg98/proceedings/cccg98-biedl-reconfiguring.ps.gz},
}

Abstract:

It is an open problem to determine whether a polygonal chain can be “straightened” in the plane if its links are not allowed to cross. This problem has been raised independently by several researchers, including J. Mitchell, and W. Lenhart and S. Whitesides [LW95]. In this paper, we propose a related question: whether a tree linkage can always be “straightened” in the plane, without allowing its links to cross. We prove that this is not always possible.

Comments:

This paper is also available from the electronic proceedings as http://cgm.cs.mcgill.ca/cccg98/proceedings/cccg98-biedl-reconfiguring.ps.gz, and as arXiv:cs/9910024.

Length:

The paper is 11 pages and the talk is 20 minutes.

Availability:

The paper is available in PostScript (467k).

See information on file formats.

[Google Scholar search]

Related papers:

LockedTreeDAM (A Note on Reconfiguring Tree Linkages: Trees can Lock)

LockedTreeTR (On Reconfiguring Tree Linkages: Trees can Lock)

Related webpages:

Carpenter's Rule Theorem