# Morphing

## Upward Planar Morphs

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 …

## How to Morph a Tree on a Small Grid

In this paper, we study planar morphs between straight-line planar grid drawings of trees. A morph consists of a sequence of morphing steps, where in a morphing step vertices move along straight-line trajectories at constant speed. We show how to …

## Morphing Contact Representations of Graphs

We consider the problem of morphing between contact representations of a plane graph. In a contact representation of a plane graph, vertices are realized by internally disjoint elements from a family of connected geometric objects. Two such elements …

## Upward Planar Morphs

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 …

## How to Morph Planar Graph Drawings

Given an $n$-vertex graph and two straight-line planar drawings of the graph that have the same faces and the same outer face, we show that there is a morph (i.e., a continuous transformation) between the two drawings that preserves straight-line …

## Optimal Morphs of Convex Drawings

We give an algorithm to compute a morph between any two convex drawings of the same plane graph. The morph preserves the convexity of the drawing at any time instant and moves each vertex along a piecewise linear curve with linear complexity. The …

## Morphing Planar Graph Drawings Optimally

We provide an algorithm for computing a planar morph between any two planar straight-line drawings of any $n$-vertex plane graph in $O(n)$ morphing steps, thus improving upon the previously best known $O(n^2)$ upper bound. Further, we prove that our …