Abstract
Annotating maps, graphs, and diagrams with pieces of
text is an important step in information
visualization that is usually referred to as label
placement. We define nine label-placement models for
labeling points with axis-parallel rectangles given
a weight for each point. There are two groups;
fixed-position models and slider models. We aim to
maximize the weight sum of those points that receive
a label. We first compare our models by giving
bounds for the ratios between the weights of
maximum-weight labelings in different models. Then
we present algorithms for labeling $n$ points with
unit-height rectangles. We show how an $O(nłog
n)$-time factor-2 approximation algorithm and a PTAS
for fixed-position models can be extended to handle
the weighted case. Our main contribution is the
first algorithm for weighted sliding labels. Its
approximation factor is $(2+\varepsilon)$, it runs
in $O(n^2/\varepsilon)$ time and uses
$O(n/\varepsilon)$ space. We show that other than
for fixed-position models even the projection to one
dimension remains NP-hard. For slider models we
also investigate some special cases, namely (a) the
number of different point weights is bounded,
(b) all labels are unit squares, and (c) the ratio
between maximum and minimum label height is
bounded.
