Special Issue on Selected Papers from the Fifteenth International Symposium on Graph Drawing, GD 2007
Algorithms for Multi-Criteria Boundary Labeling
Marc Benkert, Herman Haverkort, Moritz Kroll, and Martin Nöllenburg
Vol. 13, no. 3, pp. 289-317, 2009. Regular paper.
Abstract 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.
Submitted: December 2007.
Reviewed: June 2008.
Revised: August 2008.
Accepted: November 2008.
Final: December 2008.
Published: November 2009.
Communicated by Seok-Hee Hong and Takao Nishizeki
article (PDF)