@awolff@awolff

Three Rules Suffice for Good Label Placement

Frank Wagner, Alexander Wolff, Vikas Kapoor, and Tycho Strijk. Algorithmica 30(2):334--349 (2001)

Abstract

The general label-placement problem consists in labeling a set of features points, lines, regions given a set of candidates rectangles, circles, ellipses, irregularly shaped labels for each feature. The problem arises when annotating classical cartographical maps, diagrams, or graph drawings. The size of a labeling is the number of features that receive pairwise nonintersecting candidates. Finding an optimal solution, i.e., a labeling of maximum size, is NP-hard. \par We present an approach to attack the problem in its full generality. The key 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. We present a set of rules that simplify the conflict graph without reducing the size of an optimal solution. Combining the application of these rules with a simple heuristic yields near-optimal solutions. We study competing algorithms and do a thorough empirical comparison on point-labeling data. The new algorithm we suggest is fast, simple, and effective.

Links and resources

You can use this internal link to create references to this post in your discussions. Just copy this internal link and paste it in your discussion text.

Comments or reviews  
(0)

There is no review or comment yet. You can write one!

Tags


Cite this publication