(left) A planar graph $G$ with a red and a blue cycle. (right) The skeleton of an R-node $\mu$ of the SPQR-tree of $G$ rooted at edge $e=uv$. The blue and red cycles are relevant for $\mu$ as they project to the blue and red cycle of the skeleton, respectively. The red cycle is an interface cycle
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.
Giordano Da Lozzo
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.