Information Technology Reference
In-Depth Information
is an
R
-node of
T
,thenitisalways
OS
. In order to handle
P
-nodes,
we first need to define a special kind of
S
-nodes [11].
Observe that if
μ
Definition 2.
Let
μ
be an S-node of T . Let
ʷ
be the uniquechild of
μ
having s
μ
as a
ʷ
be the uniquechild of
pole, andlet
μ
having t
μ
as a pole. Node
μ
has a tail ats
μ
ʷ
)isa Q-node.
(t
μ
), if
ʷ
(
The next property derives from Lemma 6 in [11], see also Figure 1(b).
Property 3.
Let
μ
be an
OSP
-node of
T
. One of the following cases holds: (
i
)
μ
has
two children one of which is a
Q
-node and the other one is
OS
; (
ii
)
has two children
and none of them is a
Q
-node. Then both are
OSS
-nodes, one of them has a tail at
s
μ
,
and the other one has a tail at
t
μ
. Also, the two edges associated with these two tails
cross each other in
G
; (
iii
)
μ
has three children and one of them is a
Q
-node. For the
remaining two children case (
ii
) applies.
μ
Property 3 is restricted to
P
-nodes that are
OS
. However, an internal
P
-node
μ
(dif-
ferent from
ʾ
)might not have the edge (
s
μ
,
t
μ
) on the outer face of
G
μ
[11], see also
Figure 1(c) for an illustration.
Definition 3.
Let
μ
be aP-node of T differentfrom
ʾ
. Node
μ
is almost onesidedwith
respect to s
μ
4
children,
oneofthem is an S-node withatail ats
μ
(t
μ
), andfortheremaining children oneof
the following cases applies:
(
i
)
If k
= 2
,then theother child is OS;
(
ii
)
If k
>
2
, all and
only thecases inProperty 3can apply for theremaining k
(t
μ
), or simply AOSwith respect to s
μ
(t
μ
), if
μ
has
2
≤
k
≤
−
1
children.
be
AOS
with respect to
s
μ
(
t
μ
), then, in order to guarantee that the graph is outer
1-planar, the edge associated with the tail at
s
μ
Let
μ
(
t
μ
) crosses another edge, represented
by a
Q
-node
ˈ
in
T
,having
t
μ
(
s
μ
) as an end-vertex. This implies that in fact,
μ
and
ˈ
are two children of an
S
-node
in
T
[11] (see also Figure 1(d)). This observation will
be used in Section 3 and in the next property, that is derived from Lemma 7 in [11].
ʽ
Property 4.
Let
μ
be an
S
-node of
T
.Let
ʷ
1
,
ʷ
2
,...,
ʷ
k
be the
k
children of
μ
in
T
,such
that
t
ʷ
i
−
1
=
s
ʷ
i
,for
i
= 2
,...,
k
. For each 1
≤
i
≤
k
, one of the following cases applies:
(
i
)
ʷ
i
is
OS
; (
ii
)
ʷ
i
is
AOS
with respect to
s
ʷ
i
and
ʷ
i
+1
(
i
<
k
)isa
Q
-node; (
iii
)
ʷ
i
is
AOS
with respect to
t
ʷ
i
and
ʷ
i
−
1
(
i
>
1) is a
Q
-node.
An immediate observation from these properties is that every node
μ
of
T
different
from
ʾ
is
OS
if it is an
S
-or
R
-node, while it is either
OS
or
AOS
if it is a
P
-node.
3
The Outer 1-planar Slope Number
In this section we first present an algorithm, called BO1P-D
RAWER
, that takes as input
a biconnected outer 1-plane graph
G
with maximumdegree
ʔ
,andreturns a straight-
line drawing
slopes. This result is then extended to simply
connected graphs with a number of slopes equal to 6
ʓ
of
G
that usesatmost6
ʔ
ʔ
+ 12.
