Abstract
Graphical features on map, charts, diagrams and
graph drawings usually must be annotated with text
labels in order to convey their meaning. In this
paper we focus on a problem that arises when
labeling schematized maps, e.g. for subway
networks. We present algorithms for labeling points
on a line with axis-parallel rectangular labels of
equal height. Our aim is to maximize label size
under the constraint that all points must be
labeled. Even a seemingly strong simplification of
the general point-labeling problem, namely to decide
whether a set of points on a horizontal line can be
labeled with sliding rectangular labels, turns out
to be weakly NP-complete. This is the first labeling
problem that is known to belong to this class. We
give a pseudo-polynomial time algorithm for it. In
case of a sloping line points can be labeled with
maximum-size square labels in $O(n n)$ time if
four label positions per point are allowed and in
$O(n^3n)$ time if labels can slide. We also
investigate rectangular labels.
Users
Please
log in to take part in the discussion (add own reviews or comments).