Information Technology Reference
In-Depth Information
v
1
v
n
v
i
v
i
v
j
v
v
i
v
j
v
3
v
1
v
2
v
1
v
2
v
2
(a)
(b)
(c)
Fig. 1.
(a) Horizontal placement of a chain
P
k
=
{v
i
,...,v
j
}
.(b)Placement of a singleton
P
k
=
{v
i
}
with degree four. (c) Final layout after repositioning
v
1
and
v
2
(the shape of the
dotted edges can be obtained by extending the stubs until they intersect).
Theorem 1.
Givenatriconnected 4-planar graph
G
, wecan compute in
O
(
n
)
time an
octilineardrawing of
G
withat most 1 bend per edgeonan
O
(
n
2
)
×
O
(
n
)
integer grid.
Proof.
In order to keep the time complexity of ouralgorithm linear, we employ a simple
trick. We assume that any two adjacent points of the underlying integer grid are by
n
units apart in the horizontal direction and by one unit in the vertical direction. This
a priori ensures that all edges that contain a diagonal segment will not be involved
in crossingsandsimultaneously does not affect the total area of the drawing,which
asymptotically remains cubic. On the other hand, the advantage of this approach is that
we can use the shifting method of Kant [11] to cope with the introduction of chains in
the drawing, that needs
O
(
n
) time in total by keeping relative coordinates that can be
efficiently updated and computing the absolute values only at the last step.
The Biconnected Case.
Consider a node
μ
in the rooted SPQR-tree
T
of
G
with poles
P
μ
=
{s, t}
. In the drawing of
G
per
μ
,
s
should be located at the upper-left and
t
at the
lower-right corner of the drawing'sbounding box with a port assignment as in Fig.2a.
We also assume that the edges incident to
s
(
t
,resp.)use the western (eastern, resp.)
port at their other endpoint, except of the northern (southern, resp.) most edgewhich
may use the north (south, resp.) port instead. In that case we refer to
s
and
t
as
fixed
;
see
e
s
, e
t
in Fig.2a. We maintain the following invariants:
IP-1: The width (height) of the drawing of
μ
is quadratic (linear) in the size of
G
per
μ
.
s
is located at the upper-left;
t
at the lower-right corner of the drawing'sbounding
box.
IP-2: If
deg
per
μ
(
s
)
2,
s
is fixed;
t
is fixed if
deg
per
μ
(
t
)=3and
μ
's parent is not the
≥
root.
IP-3: The edges that are incident at
s
and
t
in
G
per
μ
use the south, south-east and east
ports at
s
and the north, north-west and west port at
t
,resp.If
s
or
t
is not fixed,
incident edges are attached at their other endpoints via the west and east port,
respectively. If
s
or
t
is fixed, the northern-most edgeat
s
and the southern-most
edgeat
t
may use the north (south, resp.) port at its other endpoint.
The port assignment, i.e. IP-3, guarantees the ability to stretch the drawing horizon-
tally even in the case where both poles are fixed. Furthermore, IP-2 is
interchangeable
in the following sense: If
deg
per
μ
(
s
)=2and
deg
per
μ
(
t
)=1,then
s
is fixed but
t
is
