Three rules suffice for good label placement

The general label-placement problem consists in labeling a set of features (points, lines, regions) given a set of candidates (rectangles, circles, el lipses, irregularly shaped labels) for each feature. The problem arises whe n annotating classical cartographical maps, diagrams, or graph drawings. Th e size of a labeling is the number of features that receive pairwise nonint ersecting candidates. Finding an optimal solution, i.e., a labeling of maxi mum size, is NP-hard. We present an approach to attack the problem in its full generality. The ke y idea is to separate the geometric part from the combinatorial part of the problem. The latter is captured by the conflict graph of the candidates. W e present a set of rules that simplify the conflict graph without reducing the size of an optimal solution. Combining the application of these rules w ith a simple heuristic yields near-optimal solutions. We study competing algorithms and do a thorough empirical comparison on poi nt-labeling data. The new algorithm we suggest is fast, simple, and effecti ve.