Invitation to the Logic Seminar at the National University of Singapore
Date: Wednesday, 10 June 2015, 17:00 hrs
Room: S17#04-04, Department of Mathematics, NUS
Speaker: Sheung-Hung Poon, National Tsing Hua University, Taiwan
Title: On Unfolding Trees of Small Diameters
Graph reconfiguration problems have wide applications in contexts
including robotics, molecular conformation, animation, wire bending,
rigidity and knot theory. The motivation for reconfiguration problems of
lattice graphs arises in applications in molecular biology and robotics.
We consider the problems of straightening polygonal trees by continuous
motions such that rigid edges can rotate around vertex joints and no edge
crossings are allowed. A tree can be straightened if all its edges can be
aligned along a common straight line such that each edge points “away”
from a designated leaf node. In this talk, we start with presenting
examples of locked trees in 2D and 3D, respectively. Then we present
“minimal” locked trees in 2D, which we discovered recently. Furthermore,
we give algorithms to unfold several special classes of diameter-4 trees
in 2D. Several interesting questions remain open. For instances, is there
a polynomial-time algorithm to determine whether a diameter-4 tree in 2D
can be straightened ? Can an equilateral tree of diameter 4 in 3D always
be straightened ?
Sheung-Hung Poon received his M.Phil. and Ph.D. degrees in
Department of Computer Science from the Hong Kong University of
Science & Technology, Hong Kong, in 1999 and 2004,
respectively. He had been a postdoc researcher in Algorithm Group at
Technical University of Eindhoven, The Netherlands, for two and a half years.
He has been an assistant professor in Department of Computer Science at
National Tsing Hua University, Taiwan, since August 2007. His research
interests include geometric algorithms, graph drawing and graph algorithms,
and their complexities.