Information Technology Reference
In-Depth Information
Morphing Schnyder Drawings
of Planar Triangulations
Fidel Barrera-Cruz
1
,PennyHaxell
1
, and Anna Lubiw
1
University of Waterloo, Waterloo, Canada
{fbarrera,pehaxell,alubiw}@uwaterloo.ca
Abstract. We consider the problem of morphing between two planar
drawings of the same triangulated graph, maintaining straight-line pla-
narity. A paper in SODA 2013 gave a morph that consists of
O
(
n
2
) steps
where each step is a linear morph that moves each of the
n
vertices in a
straight line at uniform speed [1]. However, their method imitates edge
contractions so the grid size of the intermediate drawings is not bounded
and the morphs are not good for visualization purposes. Using Schnyder
embeddings, we are able to morph in
O
(
n
2
) linear morphing steps and
improve the grid size to
O
(
n
)
× O
(
n
) for a significant class of drawings
of triangulations, namely the class of weighted Schnyder drawings. The
morphs are visually attractive. Our method involves implementing the
basic “flip” operations of Schnyder woods as linear morphs.
Keywords: algorithms, computational geometry, graph theory.
1
Introduction
Given a triangulation on
n
vertices and two straight-line planar drawings of it,
ʓ
and
ʓ
, that have the same unbounded face, it is possible to morph from
ʓ
to
ʓ
while preserving straight-line planarity. This was proved by Cairns in 1944 [6].
Cairns's proof is algorithmic but requires exponentially many steps, where each
step is a
linear morph
that moves every vertex in a straight line at uniform speed.
Floater and Gotsman [13] gave a polynomial time algorithm using Tutte's graph
drawing algorithm [19], but their morph is not composed of linear morphs so the
trajectories of the vertices are more complicated, and there are no guarantees
on how close vertices and edges may become. Recently, Alamdari et al. [1] gave
a polynomial time algorithm based on Cairns's approach that uses
O
(
n
2
) linear
morphs, and this has now been improved to
O
(
n
) by Angelini et al. [2]. The main
idea is to contract (or almost contract) edges. With this approach, perturbing
vertices to prevent coincidence is already challenging, and perturbing to keep
them on a nice grid seems impossible.
In this paper we propose a new approach to morphing based on Schnyder
drawings. We give a planarity-preserving morph that is composed of
O
(
n
2
) linear
morphs and for which the vertices of each of the
O
(
n
2
) intermediate drawings are
on a 6
n
6
n
grid. Our algorithm works for
weighted Schnyder drawings
which are
obtained from a Schnyder wood together with an assignment of positive weights
×
