Information Technology Reference
In-Depth Information
Shurazhsky and Gotsman [17]. However, their method suffers the same draw-
backs as Tutte's graph drawing method, namely that vertices and edges may
come very close together. Our intermediate drawings lie on a 6
n
×
6
n
grid where
1
vertices are at least distance 1 apart and face areas are at least
2
.
Not all straight-line planar triangulations are weighted Schnyder drawings,
but we can recognize those that are in polynomial time. The problem of extending
our result to all straight-line planar triangulations remains open. There is partial
progress in the first author's thesis [3].
This paper is structured as follows. Section 2 contains the relevant background
on Schnyder woods. Section 3 contains the precise statement of our main result,
and the general outline of the proof. In Section 4 we show that changing face
weights corresponds to a linear morph. Flips of facial triangles are handled in
Section 5 and flips of separating triangles are handled in Section 6. In Section 7
we explore which drawings are weighted Schnyder drawings.
1.1 Definitions and Notation
Consider two drawings
ʓ
and
ʓ
of a planar triangulation
T
.A
morph
between
ʓ
and
ʓ
is a continuous family of drawings of
T
,
}
t∈
[0
,
1]
, such that
ʓ
0
=
ʓ
and
ʓ
1
=
ʓ
.Wesayaface
xyz
collapses
during the morph
{ʓ
t
{
ʓ
t
}
t∈
[0
,
1]
if there
is
t ∈
(0
,
1) such that
x, y
and
z
are collinear in
ʓ
t
. We call a morph between
ʓ
and
ʓ
planar
if
ʓ
t
is a planar drawing of
T
for all
t ∈
[0
,
1].Notethatamorph
is planar if and only if no face collapses during the morph. We call a morph
linear
if each vertex moves from its position in
ʓ
0
to its position in
ʓ
1
along a
line segment and at constant speed. Note that each vertex may have a different
speed. We denote such a linear morph by
ʓ
0
,ʓ
1
.
Throughout the paper we deal with a planar triangulation
T
with a distin-
guished exterior face with vertices
a
1
,a
2
,a
3
in clockwise order. The set of interior
faces is denoted
(
T
). A 3-cycle
C
whose removal disconnects
T
is called a
sep-
arating triangle
, and in this case we define
T
F
|
C
to be the triangulation formed
by vertices inside
C
together with
C
as the exterior face, and we define
T
\
C
to
be the triangulation obtained from
T
by deleting the vertices inside
C
.
2 Schnyder Woods and Their Properties
A
Schnyder wood
of a planar triangulation
T
with exterior vertices
a
1
,a
2
,a
3
is
an assignment of directions and colours 1, 2, and 3 to the interior edges of
T
such that the following two conditions hold.
(D1) Each interior vertex has three outgoing edges and they have colours 1, 2, 3
in clockwise order. All incoming edges in colour
i
appear between the two
outgoing edges of colours
i
1 and
i
+1(index arithmetic modulo 3).
(D2) At the exterior vertex
a
i
, all the interior edges are incoming and of colour
i
.
−
