### Abstract

We prove that, given two topologically equivalent upward planar straight-line drawings of an $n$-vertex directed graph $G$, there always exists a morph between them such that all the drawings of the morph are upward planar and straight-line. Such a morph consists of $O(1)$ morphing steps if $G$ is a reduced planar $st$-graph, $O(n)$ morphing steps if $G$ is a planar $st$-graph or a reduced upward planar graph, and $O(n^2)$ morphing steps if $G$ is a general upward planar graph.

Further, we show that there exist two topologically equivalent upward planar drawings such that any upward planar morph between them consists of $\Omega(n)$ linear morphing steps.

###### Assistant Professor (RTDb)

My research interests are in Algorithm Engineering and Complexity, focused in particular on the theoretical and algorithmic challenges arising from the visualization of graphs.