Information Technology Reference
In-Depth Information
The following basic concepts and properties are due to Schnyder [16]. For any
Schnyder wood the edges of colour
i
form a tree
T
i
rooted at
a
i
. The path from
internal vertex
v
to
a
i
in
T
i
is denoted
P
i
(
v
).
(P1) If
T
i
T
i
+1
contains no directed cycle. In particular, any two outgoing paths from a
vertex
v
have no vertex in common, except for
v
, i.e.,
P
i
(
v
)
denotes the tree in colour
i
with all arcs reversed, then
T
i−
1
∪
T
i
∪
∩
P
j
(
v
)=
{
v
}
for
i
=
j
.
The
descendants
of vertex
v
in
T
i
, denoted
D
i
(
v
), are the vertices that have paths
to
v
in
T
i
. For any interior vertex
v
the three paths
P
i
(
v
)
,i
=1
,
2
,
3 partition
the triangulation into three regions
R
i
(
v
)
,i
=1
,
2
,
3,where
R
i
(
v
) is bounded
by
P
i
+1
(
v
)
,P
i−
1
(
v
) and
a
i
+1
a
i−
1
. Schnyder proved that every triangulation
T
has a Schnyder wood and that a planar drawing of
T
can be obtained from
coordinates that count faces inside regions:
Theorem 1 (Schnyder [15,16]).
Let
T
be a planar triangulation on
n
vertices
equipped with a Schnyder wood
S
. Consider the map
f
:
V
(
T
)
ₒ
R
3
,where
f
(
a
i
)=(2
n−
5)
e
i
,where
e
i
denotes the
i
-th standard basis vector in
R
3
,andfor
each interior vertex
v
,
f
(
v
)=(
v
1
,v
2
,v
3
)
,where
v
i
denotes the number of faces
contained inside region
R
i
(
v
)
.Then
f
defines a straight-line planar drawing.
Dhandapani [7] noted that the above result generalizes to weighted faces. A
weight distribution
w
is a function that assigns a positive weight to each internal
face such that the weights sum to 2
n
−
5. For any weight distribution, the above
result still holds if
v
i
is defined as:
v
i
=
{
w
(
f
):
f
∈
R
i
(
v
)
}
.
(1)
We call the resulting straight-line planar drawing the
weighted Schnyder drawing
obtained from
w
and
S
.
We now describe results of Brehm [5], Ossona De Mendez [14], and Felsner [11]
on the flip operation that can be used to convert any Schnyder wood to any
other. Let
S
be a Schnyder wood of planar triangulation
T
.Aflipoperateson
a cyclically oriented triangle
C
of
T
. We use the following properties of such a
triangle (proofs in the long version).
(S1) The triangle
C
has an edge of each colour in
S
.Furthermore,if
C
is
oriented counterclockwise then the edges along
C
have colours
i
,
i
1,
i
+1.
(S2) If
C
is a separating triangle, then the restriction of
S
to the interior edges
of
T
−
|
C
is a Schnyder wood of
T
|
C
.
Let
C
=
xyz
be oriented counterclockwise with edges
xy,yz,zx
of colour
1
,
3
,
2 respectively. A
clockwise flip
of
C
alters the colours and orientations of
S
as follows:
1. Edges on the cycle are reversed and colours change from
i
to
i
−
1.See
triangle
xyz
in Figure 3.
