Information Technology Reference
In-Depth Information
20
P
19
18
P
Q*
6
17
5
1,20
16
4
S
S
15
3
14
G
μ
2
μ
Q*
S
Q*
S
13
12
6,20
15,16,17,18,19,20
S
P
Q*
11
10
P
Q*
Q*
Q*
P
9
1,2,3
Q*
Q*
12,15
12,13,14,15
Q*
Q*
1,7,8,9
8
7
3,6
3,4,5,6
9,11,12
9,10,12
1
(a)
(b)
18
19
18
19
16
17
18
19
16
17
16
17
15
14
13
14
13
15
14
13
15
6
20
6
20
5
5
6
20
5
12
12
11
11
12
11
4
3
4
3
4
3
9
9
9
10
10
10
2
1
2
1
2
1
8
8
7
7
8
7
(c)
(d)
(e)
Fig. 4.
(a) A planar graph
G
;(b)The
SPQ
∗
-tree of
G
for the reference edge (1
,
20),andahigh-
lighted node
μ
(the pertinent graph
G
μ
of
μ
is highlighted in the graph); (c)-(d) Two rectilinear
orthogonal representations
H
and
H
that are
μ
-different; both
H
μ
and
H
μ
have spirality 2. (e)
The rectilinear orthogonal representation obtained by substituting
H
μ
with
H
μ
in
H
.
H
be two rectilinearorthogonalrepresentationsofthe
sameplanar graph
G
such that
H
Theorem 2.
[7]
Let
and
H
H
are
μ
-different and
˃
(
H
μ
)=
˃
(
H
μ
)
.Then
and
H
obtained by
substituting
H
μ
in
theembedded labeled graph
H
μ
with
H
is a recti-
linearorthogonalrepresentation.
Intuitively, Theorem 2 implies that in an orthogonal representation
H
we can always
H
μ
with a component
H
μ
substitute a certain component
having the same spirality,
H
μ
.
Spirality Relationships for Series- and Parallel-Compositions.
Let
H
μ
and
independently of the planar embedding of
be a rectlinear
orthogonal representation of
G
.Foran
S
-ora
P
-node
μ
of
T
, the spirality of
H
H
μ
is
related to the spiralities of the orthogonal representations of the pertinent graphs of the
children of
μ
.Foran
S
-node the relationship is given by Lemma 2. For a non-root
P
-node the relationship depends on the number of its children (see Lemmas 3 and 4).
Lemma 2.
[7]
Let
μ
be an
S
-node of
T
with children
μ
1
and
μ
2
.Then:
˃
(
H
μ
)=
˃
(
H
μ
2
)
.
Lemma 3.
[7]
Let
μ
be a
P
-node of
T
with three children
μ
1
,
μ
2
, and
μ
3
.Let
e
i
be
theedgeof
H
μ
1
)+
˃
(
H
μ
incident to pole
w
(
i
=1
,
2
,
3)
andlet
e
out
be the externaledgeof
H
μ
