Three rules suffice for good label placement

F. Wagner, A. Wolff, V. Kapoor, T. Strijk

    Research output: Contribution to journalArticleAcademicpeer-review

    51 Citations (Scopus)
    2 Downloads (Pure)


    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. 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.
    Original languageEnglish
    Pages (from-to)334-349
    Issue number2
    Publication statusPublished - 2001


    Dive into the research topics of 'Three rules suffice for good label placement'. Together they form a unique fingerprint.

    Cite this