Information Technology Reference
In-Depth Information
The Triconnected Case.
Let
G
=(
V,E
) be a triconnected 4-planar graph and
ʠ
=
{
be a canonical order of
G
. We momentarily neglect the edge (
v
1
,v
2
)
of the first partition
P
0
of
ʠ
and we start by placing the second partition, say a chain
P
1
=
P
0
,...,P
m
}
, on a horizontal line from left to right. Since
v
3
and
v
|P
1
|
+2
are
adjacent to
v
1
and
v
2
, we place
v
1
to the left of
v
3
and
v
2
to the right of
v
|P
1
|
+2
.So,they
form a single chain where all edges are drawn using horizontal line-segments that are
attached to the east and west port at their endpoints. The case where
P
1
is a singleton
is analogous. Having laid out the base of ourdrawing, we now place in an incremental
manner the remaining partitions. Assume that we have already constructed a drawing
for
G
k−
1
and we now have to place
P
k
,forsome
k
=2
,...,m
{
v
3
,...,v
|P
1
|
+2
}
−
1.
i
+1vertices, we draw them
from left to right along a horizontal line one unit above
G
k−
1
.Since
v
i
and
v
j
are the
only vertices that are adjacent to vertices in
G
k−
1
, both only to one, we place the chain
between those two as in Fig.1a. The port used at the endpoints of
P
k
in
G
k−
1
depends
on the following rule: Let
v
i
(
v
j
, resp.) be the neighbor of
v
i
(
v
j
,resp.)in
G
k−
1
.If
the edge (
v
i
,v
i
) ((
v
j
,v
j
), resp.) is the last to be attached to vertex
v
i
(
v
j
, resp.), i.e.,
there is no vertex
v
in
P
l
∈
In case where
P
k
=
{
v
i
,...,v
j
}
is a chain of
j
−
ʠ
,
l>k
such that (
v
i
,v
)
E
((
v
j
,v
)
E
, resp.), then
we use the northern port of
v
i
(
v
j
, resp.). Otherwise, we choose the north-east port for
(
v
i
,v
i
) or the north-west port for (
v
j
,v
j
).
In case of a singleton
P
k
=
∈
∈
, we can apply the previousrule if the singleton
is of degree three. However, if
v
i
is of degree four, then we may have to deal with an
additional third edge (
v
i
,v
) that connects
v
i
with
G
k−
1
. However, we may assume that
v
lies between the other two endpoints, thus, we place
v
i
such that
x
(
v
i
)=
x
(
v
).This
enables ustodraw(
v
i
,v
) as a vertical line-segment; see Fig.1b.
The above procedure is able to handle all chains and singletons except the last par-
tition
P
m
,as
v
n
may have 4 edges pointing downwards. We exclude (
v
n
,v
1
) and draw
v
n
as an ordinary singleton. Then, we shift
v
1
to the left and upasinFig.1c and draw
(
v
1
,v
n
) as a horizontal-vertical segment combination. Vertex
v
2
is analogously moved.
The drawings of the remaining edges incident to
v
n
are depicted in Fig.1c.
A
cut
is a
y
-monotone continuouscurve that crosses only horizontal segments and
divides the current drawing into a left and a right part. Since every edge, except the ones
drawn as vertical line-segments, contains exactly one horizontal segment, we can shift
the right part of the drawing that is defined by the cutfurther to the right while keeping
the left part of the drawing on place and the result remains a valid octilinear drawing.
To co m pute the x-coordinates, we first assign consecutive x-coordinates to the first
two partitions. We may have to stretch the drawing in two cases: (i) when we introduce a
chain, say
P
k
, as it may not fit into the gap defined by its two adjacent vertices in
G
k−
1
,
and, (ii) when an edge that contains a diagonal segment is to be drawn, to prevent it
from intersecting any horizontal-vertical combinations in the face below it. We can cope
with both cases by horizontally stretching the drawing by a factor that is bounded by
the current height of the drawing. Since the height of the resulting drawing is bounded
by
{
v
i
}
=
O
(
n
), it follows that in the worst case its width is
O
(
n
2
). Note that our
algorithm produces drawings that have a linear number of bends in total (in particular,
exactly 2
|
ʠ
|
=
O
(
n
) bends). One can prove that this bound is asymptotically tight (see
[1]). We are now ready to state the main theorem of this subsection.
|
ʠ
|
