  The usefulness of technical drawings as well as scientific illustrations such
as medical drawings of human anatomy essentially depends on the placement of
labels that describe all relevant parts of the figure. In order to not spoil or
clutter the figure with text, the labels are often placed around the figure and
are associated by thin connecting lines to their features, respectively. This
labeling technique is known as external label placement.
  In this paper we introduce a flexible and general approach for external label
placement assuming a contour of the figure prescribing the possible positions
of the labels. While much research on external label placement aims for fast
labeling procedures for interactive systems, we focus on highest-quality
illustrations. Based on interviews with domain experts and a semi-automatic
analysis of 202 handmade anatomical drawings, we identify a set of 18 layout
quality criteria, naturally not all of equal importance. We design a new
geometric label placement algorithm that is based only on the most important
criteria. Yet, other criteria can flexibly be included in the algorithm, either
as hard constraints not to be violated or as soft constraints whose violation
is penalized by a general cost function. We formally prove that our approach
yields labelings that satisfy all hard constraints and have minimum overall
cost. Introducing several speedup techniques, we further demonstrate how to
deploy our approach in practice. In an experimental evaluation on real-world
anatomical drawings we show that the resulting labelings are of high quality
and can be produced in adequate time.

Computational Geometry