Information Technology Reference
In-Depth Information
s
=
v
1
μ
1
v
2
v
i
v
i
+1
v
j
μ
i
+1
μ
j
μ
2
μ
i
μ
i
μ
3
v
4
v
3
v
i
μ
4
G
k−
1
v
j
v
5
=
t
(a)
(b)
s
s
v
i
μ
sn
μ
j
μ
i
v
n
μ
v
v
i
G
k−
1
v
v
j
t
(c)
(d)
Fig. 3.
(a) S-node with children
μ
1
,...,μ
4
;
μ
3
is a Q-node representing the edge (
v
3
,v
4
).Op-
tional edges are drawn dotted. (b) Example for a chain
v
i
,...,v
j
with virtual edges representing
μ
i
,...,μ
j−
1
in the R-node case. (c) Singleton
v
i
with possibly three incident virtual edges rep-
resenting
μ
i
,μ
v
,μ
j
.(d)Placing
v
n
and movingup
s
which might be fixed in
μ
sn
.
the edges (
v
i
,v
i
+1
)
,...,
(
v
j−
1
,v
j
) representing the children
μ
i
,...,μ
j−
1
and (
v
i
,v
i
)
((
v
j
,v
j
) resp.) representing
μ
i
(
μ
j
resp.). We place the vertices of
P
k
on a horizontal
line highenough above
G
k−
1
so that every drawing fits in-between. Then, we insert the
drawingsaligned below the horizontal line and choose for
i
l<j
,
v
l
to be the fixed
node in
μ
l
, whereas in
μ
i
(
μ
j
resp.), we set
v
i
(
v
j
resp.) to be fixed. So, for
i
≤
l<j
,
v
l
+1
may form a nose in
μ
l
pointingupwards while
v
i
and
v
j
form each one downwards
as in Fig.3b. For the extra height and width, we stretch the drawing horizontally.
In case where
P
k
=
{v
i
}
≤
,
i
=
n
is a singleton, we only outline the difference
which is a possible third edge (
v
i
,v
) to
G
k−
1
representing say
μ
v
. While the other two
involved children, say
μ
i
and
μ
j
, are handled as in the chain-case,
μ
v
requires extra
height. We place
v
i
so that
μ
v
fits below
μ
j
as in Fig.3c. Notice that
deg
pert
μ
v
(
v
i
)=1and
by IP-2 both
v
i
and
v
are not fixed in
μ
v
. So, forming a nose at
v
i
and
v
is feasible.
For the last singleton
P
k
=
P
0
, both have not been
fixed. As in the triconnected algorithm we move
s
=
v
1
above
v
n
as in Fig.3d to
accommodate the drawing of the child
μ
sn
represented by the edge (
s, v
n
).Sincewe
may require
v
n
to form a nose in
μ
sn
as in Fig.3d, we choose
s
to be fixed in
μ
sn
.By
IP-2 we are allowed to fix
s
since
t
remains unfixed. Althoughsomediagonal segments
may force us to stretch the whole drawing by its height, the height of the drawing has
been kept linear in the size of
G
per
μ
. Since we increase the width by the height a constant
number of times per step, the resulting width remains quadratic.
If there is a vertex
v
{
v
n
}
, observe that since
s, t
∈
∈
V
with deg(
v
)
≤
3, then we root
T
at a Q-node
μ
that
represents one of its three incident edges and orient the poles
{
s, t
}
such that
t
=
v
.So,
for the child
μ
of
μ
follows
deg
pert
μ
(
t
)
≤
2.Ifdeg(
v
)=4for every
v
∈
V
,thenwe
root
at a Q-node that is not adjacent to an S-node, which exists due to Lemma 2. In
both cases, we may form a nose with
t
pointing downwards.
T
