Information Technology Reference
In-Depth Information
μ
3
μ
2
μ
μ
1
μ
2
μ
4
μ
3
μ
1
s
v
1
v
2
v
3
t
s
t
s
t
(a)
(b)
(c)
Fig. 5.
(a) Layout specification;
s
and
t
are located at the bottom. (b) P-node with an (
s,t
)-
edge from a Q-node
μ
1
.
s
and
t
form a nose in
μ
2
,μ
3
. (c) S-node example with four children
μ
1
,...,μ
4
.
In case where
μ
is an S-node, we align its children
μ
1
,...,μ
l
horizontally; see
Fig.5c. The poles inherit their pertinent degree from the children. The same holds for
the property of being fixed. However, by our new invariant this is forbidden, as it re-
quires that
s
and
t
are not fixed. It is easy to see that when
μ
1
is a P-node,
s
is fixed
by the invariant in
μ
1
. In this case, we swap the roles of the poles in
μ
1
such that
s
is
not fixed. However, the other pole of
μ
1
,say
v
1
, is fixed now. Since the skeleton of an
S-node is a cycle of length at least three,
v
1
=
t
.So,
s
and
t
are not fixed in the resulting
drawing.
To co m pute a layout of an R-node
μ
, we employ the triconnected algorithm (with
s
=
v
1
and
t
=
v
2
). Let
μ
e
be a child of
μ
that corresponds to virtual edge
e
=
(
u,v
) in
G
skel
μ
. Then,
deg
pert
μ
e
(
u
)
,
deg
pert
3. When inserting the drawing of
G
pert
μ
e
,
we require at most three consecutive ports at
u
and
v
for the additional edges. As
the triconnected algorithm assigns ports in a consecutive manner based on the rela-
tive position of the endpoints, we modify the port assignment so that an edgemayhave
more than one port assigned. To do so, we assign each edge
e
=(
u,v
) in
G
skel
μ
μ
e
(
v
)
≤
apair
(
deg
pert
μ
e
(
u
)
,
deg
pert
2
that reflects the number of ports required by this
edge at its endpoints. Then, we extend the triconnected algorithm such that when a port
of
u
is assignedtoanedge
e
=(
u,v
),
deg
pert
μ
e
(
v
))
∈{
1
,
2
,
3
}
1 additional consecutive ports in
clockwise or counterclockwise order are reserved. The direction depends on the differ-
ent types of edges that we will discuss next.
The simplest type of edges are the ones among consecutive vertices
v
i
,v
i
+1
of
a chain. For each such edge we reserve the additional ports at
v
i
in counterclock-
wise and at
v
i
+1
in clockwise order; see Fig.6a. So, we can later plug the drawing
of the children into the layoutasinFig.6b withoutforming noses. In the same manner,
we reserve the ports for the edges that connect
P
k
=
μ
e
(
u
)
−
to
v
i
and
v
j
in
G
k−
1
(where
P
k
is singleton or chain), i.e., at
v
i
clockwise, (
v
j
counter-clockwise, resp.) and
at
v
i
counter-clockwise (
v
j
clockwise); see Fig.6c. In case where (
v
i
,v
i
) or (
v
j
,v
j
) is
avirtual edge, we choose the poles such that
v
i
(
v
j
resp.) is fixed in
μ
(
v
i
,v
i
)
(
μ
(
v
j
,v
j
)
resp.). Thus, we can create a nose with
v
i
(
v
j
resp.). Having exactly the ports required
at both endpoints, we insert the drawing by replacing the bend with a nose as in Fig.6d.
The remaining edges from
P
k
to
G
k−
1
in case of a singleton
P
k
=
{
v
i
,...,v
j
}
are handled
similarly; see Fig.6. During the replacement of the edges, the fixed vertex is always the
upper one. The only exception are the horizontal drawn edges of a chain, for which it
does not matter which one is fixed. Finally, we root
{
v
i
}
at an arbitrarily chosen Q-node
representing a real edge (
s, t
).Byour invariant we may construct a drawing with
s
and
t
at the bottom of the drawing'sbounding box, so that (
s, t
) has a 90
ⓦ
bend downwards.
T
