Information Technology Reference
In-Depth Information
Ta b l e 1 .
Comparison of the features of variousorderings.
biconnected
successor
bitonic
st
-ordering
yes
yes
no
biconnected shelling-
& canonical ordering
yes
no
yes
canonical ordering
no
yes
yes
bitonic
st
-ordering
yes
yes
yes
decreasing sequence. We will prove this for canonical orderings as an intermediate step
in the main section of this paper. For now we refer to this as the bitonic property.
The concept of canonical ordering has been generalized to the biconnected case.
Gutwenger and Mutzel [7] use an ordered partition of the vertices, referred to as
bi-
connected shelling order
, to create poly-line drawings in an incremental manner. A
similar but more vertex ordering-based concept is used by Harel and Sardas [9]. They
introduce the so called
biconnected canonicalordering
for drawing planar graphs in a
straight-line style. In both definitions, the constraints of the triconnected version have
been relaxed. Butthisgeneralization sacrifices an important property that is required
for some applications. In the triconnected case, every vertex
v
∈
V
k
, except for
k
=
K
,
has a neighbor in
G
G
k
. We are not aware of any canonical ordering-like approach
for the biconnected case, where this is guaranteed. In order to draw a connection to
st
-orderings, we refer to this property as the successor property. Table 1 summarizes
the orderings and their features including our contribution (
bitonic
st
-ordering
).
Another common technique for the biconnected case that can be found in the litera-
ture is to first develop an algorithm using the canonical ordering and is therefore limited
to triconnected graphs. Afterwards, the algorithm is extended to the biconnected case
using
SPQR-trees
.AnSPQR-tree
−
reflects the decomposition of a biconnected graph
G
=(
V,E
) into its
triconnected components
and their relationships [5,8]. In fact, every
triconnected component
G
μ
=(
V
μ
,E
μ
) is represented by a tree node
μ
in
T
where
G
μ
itself is called the
skeleton
of
μ
. The interrelationship between two triconnected com-
ponents is described by a pair of so called
virtualedges
.Bothvirtual edges share the
same endpoints that correspond to a
split pair
T
{
s, t
}
. A split pair
{
s, t
}
is either a pair
of adjacent nodes in
G
or a
separation pair
, i.e., the removal of
disconnects
G
.
Every
G
μ
can be categorized to be one of four types based on its structure. A bundle
of at least three parallel edges is referred to as
P-node
. In case
G
μ
is a simple cycle
of length at least three, it classifies as an
S-node
, whereas if the skeleton is a simple
triconnected graph,wecallitan
R-node
. The leaves of
{
s, t
}
T
are formed by
Q-nodes
that
are bundles of two edges, one being avirtual edge while the other corresponds to an
edgeof
G
.Usually it is convenient to root
, hence, inducing a hierarchy on the tricon-
nected components. Except for the root, every skeleton
G
μ
contains then a virtual edge
(
s, t
)
∈ E
μ
that represents a link to
μ
's parent. We refer to (
s, t
) as the
reference edge
of
μ
and to its endpoints
T
{
s, t
}
as the
poles
of
μ
. When considering a node
μ
in a rooted
SPQR-tree
T
,
μ
induces a subgraph of
G
referred to as the
pertinent graph
of
μ
.
