Information Technology Reference
In-Depth Information
2
Preliminaries
In the following, we first introduce some notations and definitions that are used through-
out this work. If not stated otherwise, we consider only simple, planar biconnected
graphs. One exception is the following definition of
st
-orderings that does not require
planarity.
Definition 1.
Let
G
=(
V,E
)
be a biconnected graphwith
s, t
∈
V
,
s
=
t
andlet
ˀ
:
V
ₒ{
1
,...,
|
V
|}
be therank of the vertices inanordering
s
=
v
1
,v
2
,...,v
n
=
t
,
i.e.,
ˀ
(
v
i
)=
i
with
1
≤
i
≤
n
.
ˀ
is called an
st
-ordering,ifforall vertices
v
∈
V
with
1
<ˀ
(
v
)
<n
,there exists
(
u,v
)
,
(
v,w
)
∈
E
with
ˀ
(
u
)
<ˀ
(
v
)
<ˀ
(
w
)
.
From now on we assume that a graph is planar and a corresponding combinatorial em-
bedding is given. In that case an
st
-ordering
ˀ
of
G
has a nice property which has been
used in the graph drawing literature extensively [4]: When considering the circular order
induced by the embedding, the set of predecessors and successors form a consecutive
sequence in the circular order of the embedding at a vertex. We denote this ordered se-
quence of successors of a vertex
v
by
S
(
v
)=
i<m
,
w
i
precedes
w
i
+1
in the circular clockwise order around
v
and
ˀ
(
v
)
<ˀ
(
w
i
) holds for
all 1
{
w
1
,...,w
m
}
such that for 1
≤
m
. This property is particularly useful in an incremental drawing procedure.
However, one has no control over which successor is placed when.
Consider a simple example where a vertex
v
has been placed that has three succes-
sors, let ussay
S
(
v
)=
≤
i
≤
. Then,
ˀ
may be chosen such that
w
2
must be
placed before
w
1
and
w
3
, i.e.,
ˀ
(
w
2
)
<ˀ
(
w
1
) and
ˀ
(
w
2
)
<ˀ
(
w
3
). This may cause
problems when attaching the edges (
v,w
1
) and (
v,w
3
),since(
v,w
2
) has already been
attached. This lack of control is avoided by the canonical ordering that is limited to
triconnected planar graphs:
{
w
1
,w
2
,w
3
}
Definition 2 ([10]).
Let
G
=(
V,E
)
be a triconnected plane graphand
(
v
1
,v
2
)
an edge
on theouter face. Let
V
1
∪···∪
V
K
be an ordered partition of
V
and
G
k
(
1
≤
k
≤
K
)
thesubgraph induced by
V
1
∪···∪
V
k
with outer face
C
k
.
V
1
∪···∪
V
K
is a canonical
ordering of
G
if:
-
V
1
=
, where
v
n
lies on theouter face andisadjacentto
v
1
.
-
Each
C
k
(
k>
1
)isa cycle containing
(
v
1
,v
2
)
.
-
Each
G
k
is biconnected andinternally triconnected.
-
Fo r
1
<k<K
oneofthetwo following conditions holds:
1.
V
k
=
{
v
1
,v
2
}
and
V
K
=
{
v
n
}
{
z
}
is a singletonwhere
z
belongsto
C
k
and has atleast one neighbor in
G
k
.
2.
V
k
=
G
−
{
z
1
,...,z
m
}
where each
z
i
(
1
≤
i
≤
m
) has atleast one neighbor in
G
G
k
, and where
z
1
and
z
m
each haveone neighbor in
C
k−
1
, andthese are
theonly two neighbors of
V
k
in
G
k−
1
.
−
Clearly, a situation as in the small example cannot occur with canonical orderings,
because of the biconnectivity of
G
k
. In fact one can go one step further and claim (as
we did in the introduction) that the partition indices of the successors when considered
in the clockwise ordering as implied by the embedding, form an increasing and then
