Information Technology Reference
In-Depth Information
1
2
1
2
3
3
Fig. 2. An instance where the East algorithm does not yield a drawing without gaps.
Left: label positions before postprocessing; Right: after postprocessing.
Sites with identical y-coordinates are processed from left to right. The vertical
parts of the leaders are drawn in the
track routing area
, that is, the vertical strip
between text and labels. The width of this track routing area is specified using
the option
routingAreaWidth
of the package. We split the labels into groups,
with labels sharing a common vertical segment being put in the same group.
This can be done by a simple linear-time algorithm. Thus the vertical segments
of the leaders in each group must be placed side by side. We draw the vertical
segments in one group with equal distances between them, using the whole width
of the track routing area.
The algorithm is even easier for
os
-leaders, a leader style that was not dis-
cussed until now. We list it here because this is the style that, for example,
LibreOce uses (see Fig. 1). Labels are placed in the same order as for
opo
-
leaders. For the leaders, we connect the site with a horizontal line segment that
extends to a fixed x-coordinate inside the margin. Then we connect the end of
the horizontal segment to the label's port with a straight-line segment.
3.4
po
-Leaders
Benkert et al. [6] developed an algorithm to compute an optimal crossing-free
labeling using
po
-leaders with respect to an arbitrary badness function. This
algorithm, which uses a dynamic programming approach, is designed for uniform
labels only. It needs
O
(
n
3
) running time and
O
(
n
2
) space.
For our application, we extend the algorithm of Benkert et al. to non-uniform
labels. To be able to work with the arbitrary heights of the labels, we need to
raster the page, that is, we define the y-coordinates on which labels may be
placed. Our algorithm yields a labeling respecting this raster with minimum
total leader length. The height of the raster can be chosen using the parameter
rasterHeight
of the Latex package. The port for each label can be chosen
arbitrarily. In the following, the ports are fixed to the center of the right side of
the labels.
Let
p
1
,...,p
n
denote the sites from top to bottom and let
r
1
,...,r
m
be
the slots obtained by rasterizing the page from top to bottom. We use a 5-
dimensional table in our dynamic program. The entry
T
[
t,b,˄,ʲ,k
] represents
the minimum length of a labeling of the
k
leftmost sites in
{
p
t
,...,p
b
}
using
