Information Technology Reference
In-Depth Information
8
7
7
5
6
5
6
3
4
4
3
2
2
1
1
(a)
(b)
Fig. 6.
(a) Adding
v
7
which has only one predecessor butright support. (b) The final straight-line
drawing produced by the modified de Fraysseix-Pach-Pollack algorithm.
only outline the approach here: during every step
k
,thealgorithm maintains a straight-
line drawing for the already placed vertices,
v
1
,...,v
k−
1
of the biconnected canonical
ordering. Similar to the original algorithm, they maintain for the contouroftheouter
face of
G
k−
1
the property that it consists only of segments with slopes +1 or
1.
Adding anewvertex
v
k
with leftmost neighbor
c
l
and rightmost neighbor
c
r
in
G
k−
1
results in a stretch of the drawing such that the edges (
v
k
,c
l
) and (
v
k
,c
r
) have slope +1
and
−
=
c
r
. In the other case, where
c
l
=
c
r
holds, i.e.,
v
k
has only one predecessor, say
u
=
c
l
=
c
r
, one has to decide if
v
k
is placed to the right or to the left of
u
. Harel and Sardas [9] introduce for those vertices
the property of having
left
or
rightsupport
. Their orderingguarantees that either the
successor or predecessor of
v
k
in the clockwise ordering around
u
has already been
placed. Since
ˀ
has by definition the same property, we may proceed similar. Avoiding
sub cases, we always try to place
v
k
to the left, i.e., choosing anew
c
l
such that
c
l
is the
predecessor of
u
=
c
r
on the contourof
G
k−
1
. However, in the case where there exists
a
w
that precedes
v
k
in
S
(
u
) and for which
ˀ
(
w
)
>ˀ
(
v
k
) holds, we have to place
v
k
to
the right by choosing
c
l
=
u
and
c
r
to be the successor of
u
on the contour. Figure 6b
shows an example generated by our implementation. Notice that in difference to the
ordering as proposed in [9], in an
st
-ordering every vertex except of
t
has a successor,
hence the faces of the drawing are y-monotone.
Next, we turn our attention to the second application:
contact representations
using
rectilinear T-shaped polygons. Alam et al. [1] recently used these as an intermediate step
to create cartograms. The idea is to represent a planar graph by touching sides of simple
interior-disjoint polygons, in this case upside-down oriented T-shaped polygons. Their
approach employs
Schnyder realizer
and their close relationship to canonical orderings.
For more details see [1]. However, we choose a different approach and consider instead
a special
visibility representation
of
G
.Weassume that the reader is familiar with the
basics of visibility representations. For an introduction, see e.g.[4].Thecommonwayto
obtain such a visibility representation can be summarized as follows: The y-coordinates
y
(
v
) of the horizontal segments that represent the vertices
v
−
1, respectively. Of course, this works only for
c
l
V
of
G
are computed
by an optimal topological ordering of a planar
st
-graph induced by an
st
-ordering.For
the x-coordinate
x
(
e
) of a vertical segment that represents an edge
e
∈
E
,thesame
procedure is repeated butonthedual planar
st
-graph. We skip the first step and choose
ˀ
itself for the y-coordinates, i.e.,
y
(
v
)=
ˀ
(
v
).Asaresult every vertex has now its own
∈
