Information Technology Reference
In-Depth Information
Definition 1 (Canonical order [11]).
Fo r agiven triconnected plane graph
G
=(
V,E
)
let
ʠ
=(
P
0
,...,P
m
)
be a partition of
V
into pathssuch that
P
0
=
{
v
1
,v
2
}
,
P
m
=
{
v
n
is a path on theouter face of
G
.For
k
=0
,...,m
let
G
k
be
thesubgraph induced by
v
n
}
and
v
2
ₒ
v
1
ₒ
i
=0
P
i
and assumeitinherits its embedding from
G
. Partition
ʠ
is a canonicalorderof
G
if for each
k
=1
,...,m
∪
1
the following hold: (i)
G
k
is biconnected, (ii) all neighbors of
P
k
in
G
k−
1
are on theouter face, of
G
k−
1
(iii) all
vertices of
P
k
have atleast one neighbor in
P
j
for some
j>k
.
P
k
is called a singleton
if
−
|
P
k
|
=1
and a chain otherwise.
of a connected graph
G
has a B-node for each
biconnected componentof
G
and a C-node for each cutvertex of
G
.Each B-node is
connected with theC-nodes that are part of its biconnected component.
B
Definition 2 (BC-tree).
The
BC-tree
An SPQR-tree [8,5] provides information about the decomposition of a biconnected
graph into its triconnected components. Every triconnected component is associated
with a node
μ
in the SPQR-tree
T
. The triconnected component itself is referred to
as the
skeleton
of
μ
, denoted by
G
skel
μ
=(
V
ske
μ
,E
ske
μ
). We refer to the degree of a
vertex
v
μ
in
G
ske
μ
as
deg
ske
μ
(
v
). We say that
μ
is an
R-node
,if
G
ske
μ
is a simple
triconnected graph. A bundle of at least three parallel edges classifies
μ
as a
P-node
,
while a simple cycle of length at least three classifies
μ
as an
S-node
. By construction
R-nodes are the only nodes of the same type that are allowed to be adjacent in
∈
V
skel
T
.
The leaves of
are formed by the
Q-nodes
. Their skeleton consists of two parallel
edges; one of them corresponds to an edgeof
G
and is referred to as
realedge
.The
skeleton edges that are not real are referred to as
virtualedges
.Avirtual edge
e
in
G
skel
μ
T
corresponds to a tree node
μ
that is adjacent to
μ
in
T
, more exactly, to another virtual
edge
e
in
G
skel
μ
is rooted at a Q-node. Hence, every skeleton (except
the one of the root) contains exactly one virtual edge
e
=(
s, t
) that has a counterpart
in the skeleton of the parent node. We call this edgethe
reference edge
of
μ
denoted
by
ref
(
μ
). Its endpoints,
s
and
t
, are named the
poles
of
μ
denoted by
.Weassume that
T
P
μ
=
{
s, t
}
.
Every subtree rooted at a node
μ
of
induces a subgraph of
G
called the
pertinent
graph
of
μ
that we denote by
G
per
μ
=(
V
per
μ
,E
per
μ
). We abbreviate the degree of a
node
v
in
G
per
μ
with
deg
per
μ
(
v
). The pertinent graph is the subgraph of
G
for which the
subtree describes the decomposition. The following lemmata provide useful properties
of SPQR-trees. Due to lack of space, their proofs are given in [1].
Lemma 1.
Let
μ
be a tree node thatisnot the root in the SPQR-tree
T
T
of a sim-
ple, biconnected,
k
-planar graph
G
and
μ
its parentin
T
.For
v
∈P
μ
,itholds that
deg
per
μ
(
v
)
2
,if
μ
is aP-oran R-node anddeg
per
μ
(
v
)
1
otherwise, i.e.
μ
≤
k
−
≤
k
−
is an S-ora Q-node.
Lemma 2.
In the SPQR-tree
T
of a planarbiconnected graph
G
=(
V,E
)
with
deg(
v
)
≥
3
for every
v
∈
V
,there exists atleast oneQ-node thatisadjacenttoaP-oran
R-node.
2
Octilinear Drawings of 4-Planar Graphs
In this section, we focus on octilinear drawingsof4-planargraphs. We first consider the
triconnected case and then we extend it to biconnected and simply connected graphs.
