Information Technology Reference
In-Depth Information
graph obtained by starting from an edge and iteratively attaching a new vertex per time
to two already adjacent vertices. A
partial2-tree
is any subgraph of a 2-tree. We give a
testing algorithm for the class of partial 2-trees, which includes series-parallel graphs.
Let
G
be an HV-graph that is a connected partial 2-tree (if
G
is not connected one
can execute the test independently on each connected component). We assume that
G
does not contain three adjacent edges with the same label (H or V), because in this case
it is trivial to conclude that
G
does not admit an HV-realization. The testing algorithm
exploits a constrained version of the algorithm described in Sec. 3 for the biconnected
components and the popular data structure known as the
block-cutvertex tree
of
G
,
which describes the decomposition of
G
into its biconnected components, also called
blocks
. A block consisting of a single edge is called a
trivialblock
.
T
has a node
v
B
for each block
B
of
G
and a node
v
c
for each cutvertex
c
of
G
; there is an arc (
v
B
,v
c
)
in
T
if
c
belongsto
B
in
G
.Akey-ingredient of our testing algorithm is the following;
the proof is easy and is omitted for space reasons.
T
Lemma 7.
Let
B
1
and
B
2
be any twoblocksof
G
andlet
ʠ
be thepath from
v
B
1
to
v
B
2
in
.Let
v
c
1
and
v
c
2
be thecutvertex-nodes on
ʠ
adjacentto
v
B
1
andto
v
B
2
,
respectively (
c
1
and
c
2
may coincide). In any planarembedding of
G
,either
c
1
is on
the externalface of
B
1
or
c
2
is on the externalface of
B
2
.
T
Let
B
beablockof
G
and
c
acutvertex of
G
that belongsto
B
.Suppose we want to
construct an HV-realization of
G
for a planar embedding where
B
has
c
on the external
face and such that some other block is attached to
c
in the external face of
B
.Todothis,
we need the angle at
c
in the external face of
B
to be greater than 90 degrees. We say
that
B
is
HV-extrovert with respect to
c
if
B
admits an HV-realization
H
B
such that: (
i
)
c
on the external face of
H
B
; (
ii
) the external angle at
c
is greater than 90 degrees. We
also say that
H
B
is
extrovert with respect to
c
. The testing algorithm works as follows:
Step 1.
Consider all degree-1 block-nodes of
and for each of these nodes
v
B
let
v
c
be
its adjacent cutvertex-node; test if
B
is HV-extrovert with respect to
c
(we explain how
to test it right after the description of Step 2); if so, store its extrovert HV-realization in
a list
L
and remove
v
B
from
T
T
,otherwisemark
B
as
not HV-extrovert
.Attheendof
T
this step remove from
all cutvertex-nodes of degree less than 2,previously attached
to some degree-1 block-node.
Step 2.
Check whether one of the following cases holds; if not repeat Step 1:
Case 1. Twoblocksthat are not HV-extrovert are found
: in this case the test is negative,
because the property of Lemma 7 cannot be satisfied in any HV-realization of
G
.
Case 2.
becomes empty
. The test is positive. Indeed, in this case there exists a planar
embedding of
G
and every block
B
has an extrovert HV-realization, stored in
L
,that
is compatible with this embedding; an HV-realization of
G
can be easily obtained by
suitably merging the extrovert HV-realizations stored in
L
.
Case 3.
T
consists of just oneblock-node
v
B
marked as not HV-extrovert
. In this case
the algorithm tests whether
B
admits any HV-realization
T
H
B
, using the algorithm de-
scribed in Sec. 3. In the affirmative case the test is positive and we can still construct an
HV-realization of
G
by suitably merging the HV-realizations stored in
L
. Namely: (
i
)
embed the HV-realization of each block that shares a cutvertex
c
with
B
insideaface
