Information Technology Reference
In-Depth Information
5
7
5
7
4
6
6
4
2
2
3
3
1
1
v
v
(a)
(b)
Fig. 1.
(a) Example in which seven successors of a vertex
v
are placed in a non-bitonic manner.
The last three edges to be attached to
v
(dashed) are separated by previously attached ones (solid).
In (b), when using abitonicordering, they appear consecutively in the embedding around
v
.
The main task, when extending a triconnected drawing procedure to a biconnected
one using SPQR-trees, can be sketched as follows. The original algorithmservesasa
basis for the case in which
μ
is an R-node. It is then modified such that each (virtual)
edge in the drawing can be replaced recursively by a drawing of the corresponding
pertinent graph. Usually a drawing has to match certain invariant properties. For S-
and P-nodes alternative methods are used. Finding a good invariant and presenting a
clear proof can be tedious work and its complexity may outweigh the description of the
original triconnected algorithm. We offer a different approach by defining a new type
of
st
-ordering whose successor lists have the aforementioned property of being bitonic.
3
The Bitonic
st
-ordering
Asequence is said to be
bitonic
, if it can be partitioned into two subsequences such that
one is monotonically increasing while the other is decreasing. More specifically:
Definition 3.
An ordered sequence
A
=
{
a
1
,...,a
n
}
is
bitonic increasing
,ifthere
exists
1
≤
k
≤
n
such that
a
1
≤···≤
a
k
≥···≥
a
n
holds and
bitonic decreasing
if
a
1
≥···≥
a
n
.Moreover, wesay
A
is bitonic increasing (decreasing) with
respect to a function
f
if
A
=
a
k
≤···≤
{
f
(
a
1
)
,...,f
(
a
n
)
}
is bitonic increasing (decreasing).
One property of bitonic sequences that is very usefulinour context is the following:
Property 1.
If a sequence
A
=
{
a
1
,...,a
n
}
is bitonic increasing (decreasing), then
the reversed sequence
A
=
{
a
n
,...,a
1
}
is bitonic increasing (decreasing) as well.
In the following, we restrict ourselves to bitonic increasing sequences. Thus, we abbre-
viate it by just referring to it as being bitonic.
Definition 4.
Let
G
=(
V,E
)
be a biconnected planar graphwithafixed embedding
and
(
s, t
)
∈
E
.Wesay an
st
-ordering
ˀ
is a
bitonic
st
-ordering
,ifateveryvertex
v
∈
V
the ordered sequence of successors
S
(
v
)=
{
w
1
,...,w
m
}
asimplied by the
embedding is bitonic with respect to
ˀ
.
An ordering with this additional property is particularly useful in an incremental algo-
rithm; the edges that correspond to those successors of a vertex
v
that have not been
placed yet, appear consecutively in the embedding around
v
.SeeFigure 1 for an exam-
ple. Next, we describe how to obtain such a bitonic
st
-ordering.
