Information Technology Reference
In-Depth Information
Proof sketch:
Let
T
be the
SPQ
∗
-tree for a given reference edge
e
. We describe an
algorithm that tests whether
G
admits an HV-realization with
e
on the external face.
Let
μ
the current node of
T
when traversing
T
from bottom to top. Let
u
and
w
be
the poles of
μ
.Thealgorithm associates with
μ
asetof
tuples
, each one corresponding
to a distinct value of spirality that an HV-realization
H
μ
of
G
μ
can have within an
HV-realization
of
G
. The size of the set of tuples associated with
μ
is
O
(
n
), since,
by definition, the absolute value of spirality of
H
H
μ
cannot exceed the length of the
shortest path from
u
to
w
in
G
μ
plus one. A tuple contains a value of spirality
˃
μ
and
an encoding of an embedding of
G
μ
for which an HV-realization of
G
μ
with spirality
˃
μ
exists; this encoding describes for a
P
-node the cyclic order of the edges of
G
μ
incident to
u
and
w
(i.e., the permutation of the edges of the skeleton of
μ
); if
μ
is
either a
Q
∗
-node or an
S
-node, the algorithm does not keep any embedding information
for
μ
(because the embedding is uniquely defined). It is sufficient to keep only one
representative tuple for each possible value of spirality, since by Theorem 2 rectilinear
orthogonal representations with the same spirality are interchangeable.
If during the bottom-up visit we obtain an empty set of tuples for a node of
T
,the
algorithm reports that
G
does not admit an HV-realization with
e
on the external face.
Otherwise, let
ʽ
be the child of the root that does not correspond to edge
e
;iftheset
of tuples of
ʽ
has a tuple whose spirality verifies the condition of Lemma 5, then the
algorithm reports that an HV-realization of
G
exists; otherwise, it reports again that
G
does not have an HV-realization with
e
on the external face. Note that, the values
ʱ
s
and
ʱ
t
in Lemma 5 are uniquely determined by the H- and V-labels once the circular
ordering of the edges around
s
and
t
is decided. If the algorithm fails on
T
, a different
edge
e
is chosen and it is executed again. The tuples of
Q
∗
-nodes are computed using
Lemma 6, and those of non-root
P
-nodes using Lemmas 3 and 4. For an
S
-node
μ
with children
μ
1
and
μ
2
, based on Lemma 2, we consider all distinct values of spirality
obtained by summingup the spiralities of a tuple of
μ
1
and of a tuple of
μ
2
.However,
if
μ
1
and
μ
2
share a pole
v
of degree 4, the H- and V-labels on the edges incident to
v
may not be compatible with some pairs of spirality values for
μ
1
and
μ
2
,andthese
pairs must be discarded.
The tuple sets for all nodes of
T
are computed in
O
(
n
2
+
Q
∗
|
|
S
|
|
P
|
n
+
|
n
) time,
denote the number of
S
-,
P
-, and
Q
∗
-nodes in
T
, respectively.
Hence, we have
O
(
n
3
)-time complexity for a specific reference edgeand
O
(
n
4
) over
all possible reference edges for
G
. If the test is positive the algorithm reconstructs an
HV-realization of
G
in
O
(
n
2
) time, by visiting
T
top-down.
If
G
has maximum vertex-degree 3, there cannot be forbidden pairs of spirality val-
ues for the children of an
S
-node, and finding its possible spiralities corresponds to
computing a Cartesian sum of two sets of integers, which takes
O
(
n
log
n
) time [3].
Hence, the overall time complexity for series-parallel HV-graphs of vertex-degree at
most 3 is
O
(
n
(
where
|
S
|
,
|
P
|
,
|
Q
|
Q
∗
|
n
)) =
O
(
n
3
log
n
).
|
S
|
(
n
log
n
)+
|
P
|
n
+
|
4
Testing Algorithm for Partial 2-Trees
We extend the HV-realizability testing algorithm described in the proof of Theorem 3
to simply connected graphs that do not contain rigid components. Namely, a 2
-tree
is a
