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

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Abstract:

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 ?

Biography:

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.