Information Technology Reference
In-Depth Information
red
,
green
and
bluetree
), such that for each internal vertex
v
, its incident edges appear
in the following clockwise order: exactly one outgoing red, an arbitrary number of in-
coming blue, exactly one outgoinggreen, an arbitrary number of incoming red, exactly
one outgoing blue, an arbitrary number of incominggreen. Each of the three outer ver-
tices
r, g, b
serves as the root of the tree in the same color and all its incident interior
edges are incoming in the respective color. For
v
V
,let
R
v
(the
red region
of
v
)de-
note the region bounded by the
vg
-path in
T
g
,the
vb
-path in
T
b
and the edge
gb
.Let
∈
R
v
|
denote the number of the interior faces in
R
v
.Thegreen and blueregions
R
v
,
R
v
are
defined analogously. Assigning
v
the coordinates (
|
R
v
|
R
v
|
R
v
|
3
results in a
|
,
|
,
|
)
∈
R
plane straight-line drawing of
G
in the plane
}
called
Schnyder drawing
. Here,
f
denotes the number of faces of
G
. For a thoroughin-
troduction to this topic, see the topic of Felsner [8].
For
ʱ, ʲ
{
x
=(
x
1
,x
2
,x
3
)
|
x
1
+
x
2
+
x
3
=
f
−
1
[0
ⓦ
,
360
ⓦ
],let[
ʱ, ʲ
] denote the corresponding counterclockwise cone of
directions. We consider drawings satisfying the following constraints.
∈
Definition 1.
Let
G
=(
V,E
)
be a planetriangulationgraphwithaSchnyder labeling.
Fo r
0
ⓦ
≤ ʱ ≤
60
ⓦ
, wecall an arbitrary planarstraight-linedrawing of
Gʱ
-Schnyder
if
for each internal vertex
v ∈ V
, its outgoing red edge has direction in
[90
ⓦ
−
ʱ
2
,
90
ⓦ
+
2
]
,
bluein
[210
ⓦ
−
2
,
330
ⓦ
+
2
]
(see Fig.5a).
According to Def. 1, classical Schnyder drawingsare60
ⓦ
-Schnyder. The next lemma
shows an interesting connection between
ʱ
-Schnyder and increasing-chord drawings.
ʱ
2
,
210
ⓦ
+
2
]
and green in
[330
ⓦ
−
ʱ
Lemma 8.
30
ⓦ
-Schnyder drawings are increasing-chord drawings.
Proof.
Let
G
=(
V,E
) be a plane triangulation with a given Schnyder labeling and
ʓ
a corresponding 30
ⓦ
-Schnyder drawing.Let
r, g, b
be the red, green and blue external
vertex, respectively, and
T
r
,T
g
,T
b
the directed trees of the corresponding color.
Consider vertices
s, t
V
. First, note that monochromatic directed paths in
ʓ
have
increasing chords by Lemma 1. Assume
s
and
t
are not connected by such a path. Then,
they are both internal and
s
is contained in one of the regions
R
t
,
R
t
,
R
t
. Withoutloss
of generality, we assume
s
∈
R
t
.The
sr
-path in
T
r
crosses the boundary of
R
t
,and
we assume withoutlossofgenerality that it crosses the blueboundary of
R
t
in
u
∈
=
t
;
see Fig. 5b. The other cases are symmetric.
Let
ˁ
r
be the
su
-path in
T
r
and
ˁ
b
the
tu
-path in
T
b
;seeFig. 5c. On the one hand,
the direction of a line orthogonal to a segment of
ˁ
r
is in [345
ⓦ
,
15
ⓦ
]
[165
ⓦ
,
195
ⓦ
].On
the other hand,
ˁ
b
is contained in a cone [15
ⓦ
,
45
ⓦ
] with apex
u
.Thus,
ˁ
−
1
b
∪
front(
ˁ
r
),
and
ˁ
r
.ˁ
−
b
is self-approaching by Fact 2. By a symmetric argument it is also self-ap-
proaching in the other direction, and hence has increasing chords.
ↆ
Planar 3-trees
are the graphs obtained from a triangle by repeatedly choosing a
(triangular) face
f
, inserting anewvertex
v
into
f
, and connecting
v
to each vertex
of
f
.
Lemma 9.
Planar 3-trees have
ʱ
-Schnyder drawingsforany
0
ⓦ
<ʱ≤
60
ⓦ
.
Proof.
We describe a recursive construction of an
ʱ
-Schnyder drawing of a planar 3-
tree. We start with an equilateral triangle and putavertex
v
in its center. Then, we align
