Information Technology Reference
In-Depth Information
possible. To be more specific, we can define new face weights
w
via the following
algorithm: Initialize
w
=
w
. While some
ʴ
i
is greater than the average
ʴ
,remove
1 from a maximum weight face of
Δ
i
and add 1 to a minimum weight face in a
region
Δ
j
whose weight is less than the average.
This completes the description of
ʓ
and
ʓ
. It remains to show that the three
linear morphs are planar. The morphs
ʓ
,ʓ
only involve changes
to the weight distribution so they are planar by Lemma 4. Consider the linear
morph
ʓ,ʓ
and
ʓ,ʓ
. The two drawings differ by a flip of a separating triangle. They
have the same weight distribution
w
which satisfies
ʴ
1
=
ʴ
2
=
ʴ
3
. By Lemmas 9,
and 10 no interior face of
T
|
C
collapses during the morph. By Theorem 7 no face
ʓ,ʓ
of
T
\
C
collapses during the morph. Thus
defines a planar morph.
7
Identifying Weighted Schnyder Drawings
In this section we give a polynomial time algorithm to test if a given straight-line
planar drawing
ʓ
of triangulation
T
is a weighted Schnyder drawing. The first
step is to identify the Schnyder wood. A recent result of Bonichon et al. [4] shows
that, given a point set
P
with triangular convex hull, a Schnyder drawing on
P
is exactly the “half-
ʘ
6
-graph” of
P
, which can be computed eciently. Thus,
given drawing
ʓ
, we first ignore the edges and compute the half-
ʘ
6
graph of
the points. If this differs from
ʓ
, we do not have a weighted Schnyder drawing.
Otherwise, the half-
ʘ
6
graph determines the Schnyder wood
S
. We next find
the face weights. We claim that there exists a unique assignment of (not neces-
sarily positive) weights
w
on the faces of
T
such that
ʓ
is precisely the drawing
obtained from
S
and
w
as described in (1). Furthermore,
w
can be found in
polynomial time by solving a system of linear equations in the 2
n
−
5 variables
w
(
f
)
,f
(
T
). The equations are those from (1). The rows of the coecient
matrix are the characteristic vectors of
R
i
(
v
)
,i
∈F
,v
an interior vertex of
T
, and the system of equations has a solution because the matrix has rank 2
n
∈{
1
,
2
,
3
}
5.
This was proved by Felsner and Zickfeld [10, Theorem 9]. (Note that their the-
orem is about coplanar orthogonal surfaces; however, their proof considers the
exact same set of equations and Claims 1 and 2 give the needed result.)
−
8 Conclusions and Open Problems
We have made a first step towards morphing straight-line planar graph drawings
with a polynomial number of linear morphs and on a well-behaved grid. Our
method applies to weighted Schnyder drawings. There is hope of extending to
all straight-line planar triangulations. The first author's thesis [3] gives partial
progress: an algorithm to morph from any straight-line planar triangulation to
a weighted Schnyder drawing in
O
(
n
) steps—but not on a nice grid.
It might be possible to extend our results to general (non-triangulated) pla-
nar graphs using Felsner's extension [8,9] of Schnyder's results. The problem of
eciently morphing planar graph drawings to preserve convexity of faces is wide
open—nothing is known besides Thomassen's existence result [18].
