  Visualizing spatial data on small-screen devices such as smartphones and
smartwatches poses new challenges in computational cartography. The current
interfaces for map exploration require their users to zoom in and out
frequently. Indeed, zooming and panning are tools suitable for choosing the map
extent corresponding to an area of interest. They are not as suitable, however,
for resolving the graphical clutter caused by a high feature density since
zooming in to a large map scale leads to a loss of context. Therefore we
present new external labeling methods that allow navigating through dense sets
of points of interest while keeping the current map extent fixed. We provide a
unified model, in which labels are placed at the boundary of the map and
visually associated with the corresponding features via connecting lines, which
are called leaders. Since the screen space is limited, labeling all features at
the same time is impractical. Therefore, at any time, we label a subset of the
features. We offer interaction techniques to change the current selection of
features systematically and, thus, give the user access to all features. We
distinguish three methods, which allow the user either to slide the labels
along the bottom side of the map or to browse the labels based on pages or
stacks. We present a generic algorithmic framework that provides us with the
possibility of expressing the different variants of interaction techniques as
optimization problems in a unified way. We propose both exact algorithms and
fast and simple heuristics that solve the optimization problems taking into
account different criteria such as the ranking of the labels, the total leader
length and the distance between leaders. We experimentally evaluate these
algorithms and discuss the three variants with respect to their strengths and
weaknesses proving the flexibility of the presented algorithmic framework.
