Information Technology Reference
In-Depth Information
4
The Planar Slope Number
In this section we describe an algorithm, called BP-D
RAWER
, that computes a planar
drawing of an outer 1-planar graph
G
, using at most 4
2
slopes. This result is then
extended to simply connected graphs with a number of slopes equal to 4
ʔ
−
4
ʔ
2
+ 12
ʔ
ʔ
+ 8.
A Universal Set of Slopes.
We start by defining a universal set of slopes that are used
by algorithm BP-D
RAWER
.Let
=
4ʔ
ʸ
≤
12
when
ʸ
and observe that 0
<
ʔ
≥
3. We
call
green slopes
the set of slopes defined as
g
i
=(
i
−
1)
ʸ
,for
i
= 1
,
2
,...,
4
ʔ
. For each
1
yellow slopes
as
y
i
,
j
=
g
i
+ arctan
tan(
g
4ʔ
)tan(
g
3
)
tan(
g
j
)
with
ʔ
−
green slope
g
i
,wedefine
2. The reason of this choice will be clarified in the proof of Lemma 10.
The union of the green and yellow slopes defines the universal set of slopes
j
= 3
ʔ
,...,
4
ʔ
−
T
ʔ
.Itis
possible to see that
g
i
<
y
i
,
j
<
g
i
+1
, for each 1
≤
i
<
4
ʔ
and 3
ʔ
≤
j
≤
4
ʔ
−
2.
Algorithm Overview.
Algorithm BP-D
RAWER
takes as input a biconnected outer 1-
plane graph
G
with maximumdegree
ʔ
and returns a planar straight-line drawing
ʓ
of
G
that uses only slopes in
T
ʔ
. As in Section 3 we construct the
SPQR
-tree
T
of
G
rooted at a
Q
-node associated with an edge that is not crossed and belongstothe
boundary of the outer face of
G
in the outer 1-planar embedding of
G
.Thenwedraw
G
by visiting
T
bottom-up. At each internal node
ʓ
μ
of
G
μ
by combining the already computed drawings of the pertinent graphs of the children
of
μ
of
T
we compute a drawing
μ
. For each drawing
ʓ
μ
we maintain the following three invariants:
Ia.
ʓ
μ
is planar.
Ib.
ʓ
μ
uses only slopes in
T
ʔ
.
Ic.
ʓ
μ
is contained in a triangle
˄
μ
such that
s
μ
and
t
μ
are placed at the corners of its base. Also,
ʲ
μ
<
(
ʔ
(
s
μ
)
−
1)
ʸ
and
ʳ
μ
<
(
ʔ
(
t
μ
)
−
1)
ʸ
,
where
ʲ
μ
and
ʳ
μ
are the internal angles of
˄
μ
at
s
μ
and
t
μ
, respectively.
As in Section 3 the root
ˁ
of
T
and its unique child
ʾ
will be handled in a special
way. Also, in order to construct
ʓ
μ
we may shift, scale and rotate the drawingsofthe
pertinent graphs of the children of
μ
. We observe that if we rotate
˄
μ
by an angle
·
ʸ
c
, with
c
integer, the resulting drawing maintains invariant
Ib
. Namely each green
slope
g
i
,for
i
= 1
,
2
,...,
4
ʔ
, used in
˄
μ
will be transformed in another green slope
g
i
+
c
=
g
i
+
c
·
ʸ =(
i
−
1 +
c
)ʸ
,where
i
+
c
is considered modulo 4
ʔ
. Similarly, any
yellow slope
y
i
,
j
will be transformed into another yellow slope
y
i
+
c
,
j
.
Before describing how the drawing of the pertinent graph of each node
is obtained
by combining the drawing of the pertinent graphs of its children, we observe that the
structural properties described in Properties 2, 3, or 4 hold, depending on the type of
μ
μ
. However, since we want to produce a planar drawing,ouralgorithm embeds each
pertinent graph in a planar way. One of the consequence of this fact is that we no longer
need to introduce
S
∗
-nodes; namely, the
P
-nodes that are
AOS
in the outer 1-planar
embedding must be embedded in a planar way and therefore they do not need to be
handled in a special way anymore. On the other hand, we need to distinguish between
R
-nodes whose poles are adjacent in
G
and
R
-nodes whose poles are not adjacent in
G
.
For this reason we introduce
R
∗
-nodes. Let
μ
be an
R
-node; if the poles
s
μ
and
t
μ
of
μ
are adjacent in
G
, then the parent
ʽ
of
μ
is a
P
-node that has (at least) another child
ʷ
that is a
Q
-node (the edge associated with
ʷ
is (
s
μ
,
t
μ
)). We replace
μ
and
ʷ
in
T
with
, that, for the sake of description, is called an
R
∗
-node
. Also, the children
a new node
˕
of
μ
become children of
˕
.If
μ
and
ʷ
were the only two children of
ʽ
,thenwealso
