Morphing Planar Graph Drawings Optimally

Abstract: 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 algorithm is optimal, that is, we show that there exist two planar straight-line drawings

G a m m a_{s}

and

G a m m a_{t}

of an

n

-vertex plane graph

G

such that any planar morph between

G a m m a_{s}

and

G a m m a_{t}

requires

O m e g a (n)

morphing steps.

Recommendations

Cited in

(27)

This page was built for publication: Morphing Planar Graph Drawings Optimally