BibSonomy :: publication :: Three Rules Suffice for Good Label Placement

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

DOI:10.1007/s00453-001-0009-7
URL:http://dx.doi.org/10.1007/s00453-001-0009-7
BibTeX key:wwks-3rsgl-01
internal link:
?
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.
search on:

Comments or reviews  
(0)

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

Tags

  • Last update 7 months ago.
  • Created 7 months ago.

Cite this publication