Algorithms for Multi-Criteria Boundary Labeling
Marc Benkert, Herman J. Haverkort, Moritz Kroll, Martin Nöllenburg · Journal of Graph Algorithms and Applications · 2009
We present new algorithms for labeling a set P of n points in the plane with labels that are aligned to one side of the bounding box of P. The points are connected to their labels by curves (leaders) that consist of two segments: a horizontal segment, and a second segment at a fixed angle with the first. Our algorithms find a collection of crossing-free leaders that minimizes the total number of bends, the total length, or any other `badness' function of the leaders. A generalization to labels on two opposite sides of the bounding box of P is considered and an experimental evaluation of the performance is included.