Information Technology Reference
In-Depth Information
w
2
w
2
w
1
w
3
w
4
w
2
w
3
w
1
w
3
μ
2
μ
3
μ
2
w
4
μ
3
μ
1
μ
4
μ
1
μ
2
μ
3
μ
4
v
v
v
v
(a)
(b)
(c)
Fig. 3.
(a) Example of virtual edges (
v,w
1
)
,...,
(
v,w
4
) in an R-node representing the tree nodes
μ
1
,...,μ
4
. (b) Mirroring the embedding of the subgraph induced by
μ
2
turning the decreasing
sequence into an increasing sequence. (c) The bitonic successor list at
v
after mirroring the em-
bedding of
μ
1
and
μ
2
.
to the P-node case, we refer to the neighbors of
v
that are contained in the subgraph
induced by
μ
i
as
w
1
,...,w
k
i
. These form a consecutive sequence in
S
(
v
), hence, we
may write
S
(
v
) as
, ..., w
1
,...,w
k
h
neighbors in
μ
h
, ..., w
1
,...,w
k
m
w
1
,...,w
k
1
S
(
v
)=
{
}
.
neighbors in
μ
1
neighbors in
μ
m
The idea now is to distinguish between two cases, depending on if either
i<h
or
i
≥
h
holds, i.e.,
w
i
is in either the increasing or decreasing partition of
S
(
v
).
Let us first consider the case
h
≤
i
:Since
ˀ
(
w
i
)
>ˀ
(
w
i
+1
) for
h
≤
i<m
,
it follows that
ˀ
(
w
k
i
)
>ˀ
(
w
i
+
1
) for all
h
i<m
, i.e., the last neighbor in the
subgraph induced by
μ
i
has a greater label than the one in
μ
i
+1
.Byourinvariantwe
may assume that
ˀ
(
w
1
)
>
≤
>ˀ
(
w
k
i
) for all
h
m
holds, i.e., with respect
to
ˀ
, we have a decreasing subsequence in
S
(
v
). Hence, the sequence
w
1
,...,w
k
m
···
≤
i
≤
is
decreasing with respect to
ˀ
.
In the second case where 1
i<h
holds, an increasing sequence is required. We
mirror the embedding of every subgraph induced by
μ
i
with 1
≤
i<h
along its poles
(
v,w
i
).Asaresult the decreasing subsequences in
S
(
v
) turn into increasing ones, i.e.,
ˀ
(
w
1
)
<
≤
<ˀ
(
w
k
i
) for all 1
i<h
(
μ
2
in Figure 3b). Notice that by Property 1
the successor list of every vertex in the mirrored subgraph remains bitonic. Now similar
to the first case, we argue that from
ˀ
(
w
i
)
<ˀ
(
w
i
+1
) it follows that
ˀ
(
w
k
i
)
<ˀ
(
w
i
+
1
)
for all 1
···
≤
i<h
.Thus, the sequence
w
1
,...,w
h−
1
≤
is increasing with respect to
ˀ
.
k
h−
1
And as a result, the sequence
w
1
,...,w
h−
1
k
h−
1
,w
1
,...,w
k
m
is bitonic with respect to
ˀ
(Figure 3c). Notice that for
v
=
s
, there exists no
i
with
ˀ
(
w
i
)
<ˀ
(
w
i
+1
),thus,
S
(
s
)
is sorted decreasingly with respect to
ˀ
as required by the invariant.
The case where
μ
is a Q-node is trivial. Both, the canonical ordering and the SPQR-
tree, can be computed in linear time, thus, the runtime follows immediately.
In the proof of the main theorem, we changed the embedding of
G
in two places. At first
in the P-node case, we had to ensure that a possible Q-node follows the reference edge
in clockwise order around
s
. Afterwards in the R-node case, we mirrored the embedding
