Inproceedings,
Labeling Subway Lines
Proc. 12th Annu. Int. Symp. Algorithms Comput. (ISAAC'01), volume 2223 of Lecture Notes in Computer Science, page 649--659. Springer-Verlag, (2001)
DOI: 10.1007/3-540-45678-3_55
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.
