Information Technology Reference
In-Depth Information
incidentto
w
; also, suppose that
e
out
,e
1
,e
2
,e
3
are encountered in this clockwise order
around
w
.Then:
˃
(
H
μ
)=
˃
(
H
μ
1
)+2=
˃
(
H
μ
2
)=
˃
(
H
μ
3
)
−
2
.
Lemma 4.
[7]
Let
μ
be anon-root
P
-node of
T
with twochildren
μ
1
,
μ
2
. Suppose that
while moving clockwise around
w
fromanexternaledgeof
H
μ
incidentto
w
,theedges
of
H
μ
1
incidentto
w
precede those of
H
μ
2
incidentto
w
.Foreach pole
v
∈{
u,w
}
andfor
i
=1
,
2
,let
e
out
be the externaledgeof
H
μ
incidentto
v
thatiscircularly
H
μ
i
incidentto
v
, andlet
l
v
be thelabel of the
angle at
v
formed by
e
out
and
e
i
. Also, let
ʱ
v
=0
if
l
v
=
F
and
ʱ
v
=1
if
l
v
=
R
.Then:
(
i
)
˃
(
consecutive around
v
to an edge
e
i
of
k
i
w
ʱ
w
,
where
k
v
=1
if
indeg
μ
i
(
v
)=1
and
outdeg
μ
(
v
)=1
, while
k
v
=1
/
2
otherwise.
H
μ
1
)+
k
u
ʱ
u
+
k
i
w
ʱ
w
and
(
ii
)
˃
(
k
u
ʱ
u
−
H
μ
)=
˃
(
H
μ
)=
˃
(
H
μ
2
)
−
Finally, if
μ
is the root node it has two children, one of which is associated with the
reference edge
e
(see, e.g., Figs. 4(a) and 4(b)). The following result comes immediately
from [7], considering that in a rectilinear orthogonal representation each edge(included
e
)isasegment, and the number of angles with
R
-labels minusthenumber of angles
with
L
-labels in an internal face equals 4.
Lemma 5.
Let
μ
be the root of
T
andlet
ʽ
be thechild of
μ
that does not correspondto
the reference edge
(
s, t
)
.Let
f
be theinternalface of
thatcontains
(
s, t
)
, andlet
l
s
(resp.
l
t
)bethelabelofthe angle in
f
at vertex
s
(resp. at vertex
t
). Assumethat moving
along
e
from
s
to
t
corresponds to walking counterclockwise on theboundary of
f
.For
v
H
∈{
s, t
}
,let
ʱ
v
=0
if
l
v
=
F
,
ʱ
v
=1
if
l
v
=
R
, and
ʱ
v
=
−
1
if
l
v
=
L
.Then:
˃
(
H
ʽ
)+
k
s
ʱ
s
+
k
t
ʱ
t
=4
, where
k
v
=1
if
indeg
ʽ
(
v
)=1
and
k
v
=0
otherwise.
Spirality and HV-realizations.
Let
G
be an HV-graph and let
T
be an
SPQ
∗
-tree of
G
for a reference edge
e
=(
s, t
). W.l.o.g, from now on we assume that for any 2-
degree vertex
v
the two edges incident to
v
have different labels (otherwise, they can
be simply replaced by a single edge with the same label as the original edges). With
this assumption, the chain associated with a
Q
∗
-node always consists of an alternated
sequence of H-labeled and V-labeled edges. The following lemma can be easily proved.
Lemma 6.
Let
μ
be a
Q
∗
-node of
T
andlet
k
be the number of edges of
G
μ
.If
k
is
even (resp. odd), then there exists an HV-realization of
G
μ
with spirality
j
,forevery
odd (resp. even)
j
∈
[
−
k
+1
,k
−
1]
.
Testing Algorithm.
Let
G
be a series-parallel HV-graph and let
T
be the
SPQ
∗
-tree
for a given reference edge
e
=(
s, t
). The testing is done by traversing
T
bottom-up;
if the test fails,
G
does not admit an HV-realization with
e
on the external face, a new
reference edge is chosen and the test is repeated. If the test succeed for some reference
edgeof
G
,thealgorithm reconstructs an HV-realization of
G
with a top-down visit of
T
,
exploiting suitable information stored in the nodes of
T
during the bottom-up traversal.
Theorem 3.
Let
G
be a series-parallel HV-graphwith
n
vertices and maximum vertex-
degree four. There exists an
O
(
n
4
)
-time algorithm thattestswhether
G
admits an HV-
realizationand, if so, it computes an HV-realization of
G
. Also, if
G
has vertex-degree
at most
3
,thetime-complexity can be reduced to
O
(
n
3
log
n
)
.
