Information Technology Reference
In-Depth Information
i<m
for which
ˀ
(
w
i−
1
)
>ˀ
(
w
i
) and
ˀ
(
w
i
+1
)
>ˀ
(
w
i
) holds. Furthermore, let
w.l.o.g.
ˀ
(
w
i−
1
)
<ˀ
(
w
i
+1
). Notice that by construction of
ˀ
and
S
(
v
), it follows
that
ˀ
(
w
i−
1
)
=
ˀ
(
w
i
+1
).SeeFigure 2a for the initial situation at
v
.Nowweset
k
=
ˀ
(
w
i−
1
) and
k
=
ˀ
(
w
i
+1
) and argue that in a canonical ordering this can only
occurfor
k
=2. By definition of the canonical ordering,
w
i−
1
∈
V
k
hastobeinthe
outer face of
G
k−
1
as displayed in Figure 2b. Similarly,
w
i
+1
∈
V
k
has to be in the
outer face of
G
k
−
1
(see Figure 2c). As a result, the outer face of
G
k−
1
must be on both
sides of the edge (
v,w
i
) and there is only one such
G
k−
1
for which this is the case,
namely
G
1
. Hence,
k
=2,
v
=
s
,
w
i
=
s
and
w
i
+1
=
t
. However, we defined
S
(
s
)
such that it ends with
w
m
=
s
which is a contradiction.
It remains to show that all
S
(
v
) are not only bitonic with respect to
ˀ
,butalso
for
ˀ
. As aforementioned, by construction of
ˀ
from
ˀ
, for two vertices
u,v
V
with
ˀ
(
u
)
<ˀ
(
v
) it follows that
ˀ
(
u
)
<ˀ
(
v
). And since we have just shown for
the successor list
S
(
v
)=
∈
V
it holds that
ˀ
(
w
i−
1
)
<ˀ
(
w
i
) or
ˀ
(
w
i
+1
)
<ˀ
(
w
i
),wemaydeduce that
ˀ
(
w
i−
1
)
<ˀ
(
w
i
) or
ˀ
(
w
i
+1
)
<ˀ
(
w
i
). Hence, every
S
(
v
) is bitonic with respect to
ˀ
.
{
w
1
,...,w
i
,...,w
m
}
of every vertex
v
∈
The proof is constructive and reveals one additional property: The successor list of
s
is a special case, because it contains
s
and
t
.Furthermore,
s
is the only vertex with
ˀ
(
s
)
<ˀ
(
s
) and for every vertex
v
=
t
,
ˀ
(
v
)
<ˀ
(
t
) holds. Since the
successor list of
s
starts with
t
, ends with
s
by our construction, and is bitonic with
respect to
ˀ
, we can state the following:
Corollary 1.
Thesuccessor list of
s
starts with
t
,ends with
s
and is sorted decreas-
inglywith respect to
ˀ
, i.e.,
S
(
s
)=
{t, w
2
,...,w
m−
1
,s
}
∈
V
with
v
such that
ˀ
(
t
)
>ˀ
(
w
2
)
>
>ˀ
(
w
m−
1
)
>ˀ
(
s
)
.
While the above results follow the intuition of canonical orderings, they hold only for
the case where the input is triconnected. Next, we extend this result to the biconnected
case using SPQR-trees. Corollary 1 provides us with the necessary ingredient for an
invariant. More details are given in the proof of the main result of this section:
···
Theorem 1.
Every biconnected planar graph
G
=(
V,E
)
has a bitonic
st
-ordering
ˀ
for any given
st
-edge
e
∗
∈
E
.Theordering
ˀ
and a corresponding embedding can be
computed in time
O
(
|
V
|
)
.
Proof.
The overall challengeistorecursively compose a bitonic
st
-ordering along an
SPQR-tree. For a subtree, we assume that we have already constructed a bitonic
st
-
ordering that complies with an invariant. Then we show that we can combine it in the
skeleton of the parent node with the solutions of other subtrees.
Invariant:
For the assignment of an index in
ˀ
, we maintain a single global counter
that we use to label the vertices in an incremental manner. The poles
of a tree
node
μ
are labeled by the parent. Moreover,
s
has already been labeled such that we
may assume that the global counter has a value greater than
ˀ
(
s
).Furthermore,
ˀ
is a
bitonic
st
-ordering for the subgraph induced by
μ
when assigning
t
the current value
of the counter. Additionally, the successor list of
s
is sorted decreasingly with respect
to
ˀ
. We start by embedding
G
, creating the SPQR-tree
{
s, t
}
and rooting it at the Q-node
representing the given
st
-edge
e
∗
=(
s
∗
,t
∗
). Then we initialize the global counter,
T
