Information Technology Reference
In-Depth Information
A Universal Set of Slopes.
We d e fi n e a universal set of slopes used by algorithm
BO1P-D
RAWER
to draw every biconnected outer 1-plane graph
G
with maximumde-
gree
=
2ʔ
ʱ
≤
6
when
and observe that 0
<
ʔ
≥
ʔ
.Let
ʱ
3. We call
blue slopes
the set of slopes defined as
b
i
=(
i
−
1)
ʱ
,for
i
= 1
,
2
,...,
2
ʔ
. For each of the 2
ʔ
blue slopes, we also define two
red slopes
as
r
i
=
b
i
and
r
i
=
b
i
+
−
ʵ
ʵ
,for
i
=
1
,
2
,...,
2
ʔ
,wherethevalueof
ʵ
only depends on
ʔ
.Theunion of the blueandred
slopes defines the universal set of slopes
S
ʔ
of size 6
ʔ
. We choose
ʵ
as follows:
arctan
)
. The reason of this choice will be clari-
tan(ʱ)
ʵ
=
ʱ
−
1+2tan(2
ʱ
)tan(
ʱ
)
−
2tan(
ʱ
)tan(
ʱ
fied in the proof of Lemma 3. Clearly,
ʵ
depends only on
ʔ
and it is possible to see that
it is a positive value.
Algorithm Overview.
Algorithm BO1P-D
RAWER
exploits
SPQR
-trees and the struc-
tural properties presented in Section 2. It takes as input a biconnected outer 1-plane
graph
G
with maximumdegree
ʔ
and returns a straight-line drawing
ʓ
of
G
that uses
only slopes in
S
ʔ
. We first construct the
SPQR
-tree
T
rooted at a
Q
-node
ˁ
, whose
(only) child is denoted by
is not crossed and
belongs to the boundary of the outer face of
G
.Thenwedraw
G
by visiting
T
bottom-
up, handling
ʾ
. Moreover, the edge associated with
ˁ
ˁ
and
ʾ
together as a special case. At each step we process an internal
node
ʓ
μ
of its pertinent graph
G
μ
by properly combin-
ing the already computed drawings of the pertinent graphs of the children of
μ
of
T
and compute a drawing
μ
.Let
s
μ
and
t
μ
be the poles of
μ
. With a slight overload of notation for the symbol
ʔ
, we denote
by
ʔ
(
s
μ
) and
ʔ
(
t
μ
) the degree of
s
μ
and
t
μ
in
G
μ
, respectively. For each drawing
ʓ
μ
we
aim at maintaining the following three invariants.
I1.
ʓ
μ
is outer 1-plane with respect to
the embedding of
G
μ
.
I2.
ʓ
μ
uses only slopes in
S
ʔ
.
I3.
ʓ
μ
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
μ
.
We now explain how to compute a drawing
ʓ
μ
of
G
μ
, by combining the drawings
ʓ
ʷ
1
,
ʓ
ʷ
2
,...,
of the pertinent graphs
G
ʷ
1
,
G
ʷ
2
,...,
G
ʷ
h
1
,
2
,...,
ʓ
ʷ
h
of the children
ʷ
ʷ
ʷ
h
ʓ
ʷ
1
,
ʓ
ʷ
2
,...,
of
μ
. To this aim, the drawings
ʓ
ʷ
h
are possibly manipulated. First, observe
that the triangle
˄
ʷ
j
(1
≤
j
≤
h
) can be arbitrarily scaled without modifying the slopes
used in
ʓ
ʷ
j
.Furthermore, due to the symmetric choice of the blue and red slopes, if we
rotate
, with
c
integer, the resulting drawing maintains invariant
I
2. Namely each blue slope
b
i
,for
i
= 1
,
2
,...,
2
˄
ʷ
j
by an angle
c
·
ʱ
ʔ
, used in
˄
ʷ
j
will be transformed in
another blue slope
b
i
+
c
=
b
i
+
c
·
ʱ
=(
i
−
1 +
c
)
ʱ
,where
i
+
c
is considered modulo
2
. Similarly, any red slope will be transformed into another red slope. Moreover, let
ʷ
1
and
ʔ
.Whenwedraw
G
ʷ
1
and
G
ʷ
2
, although they may share
one or both the poles, we consider each graph to have its own copy of its poles. Then,
when computing
ʷ
2
be two children of
μ
ʓ
μ
, we say that we
attach
ʓ
ʷ
1
to
ʓ
ʷ
2
if they share either two poles (this
is always truewhen
μ
is a
P
-node) or one pole (this may happen when
μ
is either an
S
-or
R
-node), meaning that we may scale, shift and rotate
ʓ
ʷ
1
or
ʓ
ʷ
2
in such a way that
the points representing the shared poles on the drawing coincide.
As observed in Section 2, all the internal nodes of
T
are
OS
except for some
P
-nodes
which are
AOS
.Let
μ
be any of these
P
-nodes, we know that
μ
is one of the children
of an
S
-node, say
ʽ
, and it shares a pole with a
Q
-node, denoted by
ʷ
(also a children
of
ʽ
). We replace
μ
and
ʷ
in
T
with a new node
˕
, that, for the sake of description,
is called an
S
∗
-node
. Also, the children of
μ
become children of
˕
.If
μ
and
ʷ
were
