Information Technology Reference
In-Depth Information
with slope
b
2ʔ
−
1
=
(ʔ
−
1)ˀ
ʔ
one can prove that the line
passing through
t
μ
does not
cross the drawing of
ʓ
ʷ
.Since
ʔ
(
t
μ
)=
ʔ
(
t
ʷ
k
)+1, and
ʳ
μ
=
ʳ
ʷ
k
+
ʱ
<
(
ʔ
(
t
ʷ
k
)+1)
ʱ
+
ʱ
=(
ʔ
(
t
ʷ
k
)+2)
ʱ
=(
ʔ
(
t
μ
)+1)
ʱ
,Invariant
I3.
holds.
Lemma 4.
Let
μ
be an R-node differentfrom
ʾ
.ThenG
μ
admits a straight-linedraw-
ing
ʓ
μ
that respects Invariants
I1.
,
I2.
and
I3
.
Proof.
Refer to Figure 2(e). Recall that, by Property 2, (
i
) the skeleton
˃
(
μ
) is isomor-
phic to
K
4
and it has one crossing; (
ii
) the children of
μ
are all
OS
; (
iii
) two children
of
μ
are
Q
-nodes whose associated edges cross each other in
G
μ
. Hence, denote by
ʷ
1
,
ʷ
2
,
ʷ
3
the three children of
μ
whose associated virtual edges lie on the boundary of
the outer face of
˃
(
μ
) with
s
μ
=
s
ʷ
1
,
t
ʷ
1
=
s
ʷ
2
,
t
ʷ
2
=
s
ʷ
3
,and
t
ʷ
3
=
t
μ
. Also, denote by
ʷ
4
and
that are
Q
-nodes whose associated edges cross each
other in
G
μ
, and so that the poles of
ʷ
5
the two children of
μ
ʷ
4
coincides with
t
ʷ
1
and
t
ʷ
3
, while the poles of
ʷ
5
coincides with
t
ʷ
2
and
s
ʷ
1
.Werotate
ʓ
ʷ
1
in such a way that the segment
s
ʽ
1
t
ʽ
1
uses the
blue slope
b
2
. Similarly, we rotate
ʓ
ʷ
3
in such a way that the segment
s
ʷ
3
t
ʷ
3
uses the
blue slope
b
2ʔ
.Furthermore, we scale one of the two drawingssothat
t
ʷ
1
and
s
ʷ
3
are
horizontally aligned. Moreover, we redraw the edge associated with
ʷ
4
by using the red
slope
r
2ʔ
ʷ
5
by using the red slope
r
2
.Observe
and we redraw the edge associated with
that, attaching
ʷ
4
and
ʷ
5
to
ʷ
1
and
ʷ
3
,thelength of the segment
t
ʷ
1
s
ʷ
3
is determined.
Thus, we attach
ʓ
ʷ
2
so that
s
ʷ
2
coincides with
t
ʷ
1
and that
t
ʷ
2
coincides with
s
ʷ
3
.
It is easy to see that Invariant
I1.
and
I2.
are respected by construction. Concerning
Invariant
I3.
,againbyconstruction
˄
μ
such that
s
μ
and
t
μ
are placed at the corners of its base. Moreover, with the same argument used in
the proof of Lemma 3, one can show that
ʓ
μ
is contained in a triangle
ʲ
μ
=
ʲ
ʷ
1
+
ʱ
and that
ʳ
μ
=
ʳ
ʷ
3
+
ʱ
.Since
ʔ
(
s
μ
)=
ʔ
(
ʷ
1
)+1and
ʔ
(
t
μ
)=
ʔ
(
ʷ
3
)+1, Invariant
I3.
holds.
Lemma 5.
Let
ˁ
be the root of T andlet
ʾ
be its uniquechild. GraphG
=
G
ˁ
∪
G
ʾ
admits a straight-linedrawing
that respects Invariants
I1.
,
I2.
and
I3
.
Proof sketch:
It is possible to prove that at least one edge (
s
,
t
) of the outer face of
G
is
not crossed. If we root
T
at the
Q
-node associated with (
s
,
t
), the root's child
ʓ
ʾ
is
OS
and a drawing of
G
ˁ
∪
G
ʾ
can be computedasinLemmas1,2,3,and4.
Lemma 6.
Let G be a biconnected outer
1
-plane graphwithnvertices and withmax-
imum degree
. Gadmits an outer
1
-planarstraight-linedrawing that maintainsthe
given outer
1
-planarembedding, andthat uses at most
6
ʔ
ʔ
slopes. Also, this drawing
can be computed in O
(
n
)
time.
Proof sketch:
ByLemmas1,2,3,4,and5,
G
has an outer 1-planar straight-line drawing
that maintains the embedding, with at most 6
ʔ
slopes.
A simply connected outerplane graph can be augmented (in linear time) into a bi-
connected outerplane graph by adding edges so that the maximumdegree is increased
by at most two. This technique can be directly applied also to outer 1-plane graphs.
Theorem 1.
Let G be an outer
1
-plane graphwithnvertices and withmaximum degree
ʔ
. Gadmits an outer
1
-planarstraight-linedrawing that maintainsthe given outer
1
-
planarembedding, andthat uses at most
6
ʔ
+ 12
slopes. Also, this drawing can be
computed in O
(
n
)
time.
