Information Technology Reference
In-Depth Information
of
G
with angle at
c
larger than 90 degrees (such a face always exists, because
c
has
degree at most 3 in
B
); (
ii
) merge the extrovert HV-realizations of the other blocks as
in Case 2. If
B
does not admit any HV-realization, then the test is clearly negative.
We now explain how to test whether a block
B
is HV-extrovert with respect to a
desired cutvertex
c
.If
B
is trivial (i.e., a single edge) the test is clearly positive. If
B
is
not trivial, then
c
has degree greater than 2 in
G
and we distinguish between two cases:
Vertex
c
has Degree
3
in
G
.
In this case
c
has degree 2 in
B
.Let
s
and
u
be the two
vertices adjacent to
c
in
B
,andlet
T
be the
SPQ
∗
-tree of
B
with reference edge (
s, c
).
Execute an HV-realizability testing of
B
with respect to
T
, using the algorithm of Sec. 3.
If the test is negative,
B
does not have an HV-realization with
c
on the external face,
and we conclude that
B
is not HV-extrovert with respect to
c
. If the test is positive, there
exists an HV-realization
H
B
with
c
on the external face, butwehavetoverifythatwe
can get an HV-realization with the external angle at
c
greater than 90 degrees. If edges
(
s, c
) and (
u,c
) have the same label (H or V), we do not need to do any additional check,
as
H
B
surely has two angles of 180 degrees at
c
.If(
s, c
) and (
u,c
) have different labels,
let
ʽ
be the child-node of the root of
T
that does not correspond to the reference edge;
it suffices to check whether
ʽ
has a tuple whose spirality value satisfies the equation of
Lemma 5, with the constraint that
ʱ
c
(i.e.,
ʱ
t
of Lemma 5) is 1 (corresponding to an
internal angle at
c
of 90 degrees, and hence to an external angle at
c
of 270 degrees).
Vertex
c
has degree
4
in
G
.
If
c
has degree 2 in
B
,thealgorithm applies the same check
as in the previous case. If
c
has degree 3 in
B
,let
e
=(
s, c
) and
e
=(
u,c
) be the edges
of
B
incident to
c
with the same label (H or V), and let
e
=(
v,c
) be the third edge
of
B
incident to
c
.Let
T
be the
SPQ
∗
-tree of
B
with reference edge
e
=(
s, c
).Note
that
T
has a
P
-node
μ
such that one of its poles is
c
and such that
G
μ
contains both
e
and
e
. Also, in any HV-realization that is extrovert with respect to
c
,
e
and
e
must
be both on the external face. Hence, to check whether
B
is HV-extrovert with respect
to
c
, we can execute an HV-realizability testing of
B
on tree
T
, using the algorithm of
Sec. 3, with the restriction that when we compute the tuple set of
μ
we only consider
the arrangement of its children corresponding to having
e
on the external face.
Aboutthecomputational complexity of the test described above, let
n
be the number
of vertices of
G
,let
B
1
,B
2
,...,B
h
be the biconnected components of
G
,andlet
n
i
be the number of vertices of
B
i
(
i
=1
,...,h
). Also, let
T
the block-cutvertex tree
,thealgorithm takes
O
(
n
i
3
) to test whether
B
i
is
HV-extrovert with respect to a desired cutvertex using the algorithm of Sec. 3, as it only
needs to test the HV-realizability of
B
i
for a suitably chosen reference edge. Also, if one
block
B
i
is not HV-extrovert, an additional HV-realizability testing on
B
i
is run over
of
G
. For each block-node
v
B
i
of
T
all possible reference edges, spending
O
(
n
i
4
) time. Since
i
=1
,...,h
n
i
=
O
(
n
),the
overall time complexity of the algorithm is
O
(
n
4
). The time complexity is reduced to
O
(
n
3
log
n
) if
G
has vertex-degree at most 3, with the same argument as in Theorem 3.
Theorem 4.
Let
G
be an HV-graph thatisa partial2-treewith
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
)
.
