On straightening low-diameter unit trees

S.H. Poon

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

7 Citaten (Scopus)

Samenvatting

A polygonal chain is a sequence of consecutively joined edges embedded in space. A k-chain is a chain of k edges. A polygonal tree is a set of edges joined into a tree structure embedded in space. A unit tree is a tree with only edges of unit length. A chain or a tree is simple if non-adjacent edges do not intersect. We consider the problem about the reconfiguration of a simple chain or tree through a series of continuous motions such that the lengths of all tree edges are preserved and no edge crossings are allowed. A chain or tree can be straightened if all its edges can be aligned along a common straight line such that each edge points "away" from a designed leaf node. Otherwise it is called locked. Graph reconfiguration problems have wide applications in contexts including robotics, molecular conformation, rigidity and knot theory. The motivation for us to study unit trees is that for instance, the bonding-lengths in molecules are often similar, as are the segments of robot arms.
Originele taal-2Engels
TitelGraph Drawing (13th International Symposium, GD'05, Limerick, Ireland, September 12-14, 2005, Revised papers)
RedacteurenP. Healy, N.S. Nikolov
Plaats van productieBerlin
UitgeverijSpringer
Pagina's519-521
ISBN van geprinte versie3-540-31425-3
DOI's
StatusGepubliceerd - 2006

Publicatie series

NaamLecture Notes in Computer Science
Volume3843
ISSN van geprinte versie0302-9743

Vingerafdruk

Duik in de onderzoeksthema's van 'On straightening low-diameter unit trees'. Samen vormen ze een unieke vingerafdruk.

Citeer dit