printable pdf
比利时vs摩洛哥足彩 ,
university of california san diego

****************************

combinatorics seminar

penny haxell

university of waterloo

morphing planar graphs

abstract:

consider two straightline planar drawings g and h of the same planar triangulation, in which the outer face is fixed. a morph between g and h is a continuous family of drawings of the triangulation, beginning with g and ending with h. we say a morph between g and h is planar if each intermediate drawing is a straightline planar drawing of the triangulation. a morph is called linear if each vertex moves from its initial position in g to its final position in h along a line segment at constant speed. it is easy to see that in general the linear morph from g to h will not be planar. here we consider the algorithmic problem of finding a planar morph between two given drawings g and h with fixed outer face. for various reasons it is desirable to find morphs in which each vertex trajectory is fairly simple. thus we focus on the problem of constructing a planar morph consisting of a polynomial number of steps, in which each step is a planar linear morph. (joint work with fidel barrera-cruz and anna lubiw)

host: jacques verstraete

february 25, 2015

2:00 pm

ap&m 6402

****************************