Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
A Combinatorial Framework for Map Labeling
| Book Series | Lecture Notes in Computer Science |
| Publisher | Springer Berlin / Heidelberg |
| ISSN | 0302-9743 (Print) 1611-3349 (Online) |
| Volume | Volume 1547/1998 |
| Book | Graph Drawing |
| DOI | 10.1007/3-540-37623-2 |
| Copyright | 1998 |
| ISBN | 978-3-540-65473-5 |
| DOI | 10.1007/3-540-37623-2_24 |
| Pages | 316-331 |
| Subject Collection | Computer Science |
| SpringerLink Date | Thursday, January 01, 1998 |
| |
|
A Combinatorial Framework for Map Labeling
Frank Wagner5  and Alexander Wolff5
| (5) |
Institut fr Informatik, Fachbereich Mathematik und Informatik, Takustrae 9, D-14195, Germany |
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.
This work was supported by the Deutsche Forschungsgemeinschaft (DFG) under grants Wa 1066/1-1, 3-1, and 3-2
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|