A combinatorial framework for map labeling

F. Wagner, A. Wolff

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    15 Citations (Scopus)

    Abstract

    The general map labeling problem consists in labeling a set of sites (points, lines, regions) given a set of candidates (rectangles, circles, ellipses, irregularly shaped labels) for each site. A map can be a classical cartographical map, a diagram, a graph or any other figure that needs to be labeled. A labeling is either a complete set of non-conflicting candidates, one per site, or a subset of maximum cardinality. Finding such a labeling is NP-hard. We present a combinatorial framework to attack the problem in its full generality. The key idea is to separate the geometric from the combinatorial part of the problem. The latter is captured by the conflict graph of the candidates and by rules which successively simplify this graph towards a near-optimal solution. We exemplify this framework at the problem of labeling point sets with axis-parallel rectangles as candidates, four per point. We do this such that it becomes clear how our concept can be applied to other cases. We study competing algorithms and do a thorough empirical comparison. The new algorithm we suggest is fast, simple and effective.
    Original languageEnglish
    Title of host publicationGraph Drawing (6th International Symposium, GD'98, Montreal, Canada, August 13-15, 1998)
    EditorsS. Whitesides
    Place of PublicationBerlin
    PublisherSpringer
    Pages316-331
    ISBN (Print)3-540-65473-9
    DOIs
    Publication statusPublished - 1998

    Publication series

    NameLecture Notes in Computer Science
    Volume1547
    ISSN (Print)0302-9743

    Fingerprint

    Dive into the research topics of 'A combinatorial framework for map labeling'. Together they form a unique fingerprint.

    Cite this