Speaker : Milosz Muszynski, Ph.D. student at Carleton University
Time:     Tuesday October 9 at 14:30
Place:    HP4369 School of Math and Stats, Carleton University

Title: Diagonal flips in triangulations and rotation on rooted trees.

Abstract:
We consider a plane graph G to be a plane unlabelled triangulation 
if every face of G is bounded by a triangle. By the classical result 
of Wagner and a more recent result of Komuro two unlabelled planar 
triangulations on the same number of vertices can be transformed 
into each other by a finite sequence of diagonal flips with a
linear bound on the maximum number of flips. It has been recently 
proven by Gao, Urrutia, and Wang that for labelled planar triangulations 
the bound is O( n log n). We will talk about basic definitions, results 
and tricks on diagonal flips and triangulations. We will investigate
the relation between diagonal flips in triangulations and rotations on
rooted trees. Next, we will consider the differences between flips in 
labelled and unlabelled triangulations. We will delve into more detail 
when discussing the proof for the upper bound of the number of flips
needed to transform labelled triangulations. Finally, we will talk about 
some interesting problems related to the question of optimality of this 
bound. New ideas for proving the optimality of this bound will be discussed.