Randbeschriftungen

Randbeschriftungen werden z.B. beim Beschriften von Orten oder Regionen in Landkarten benutzt, wenn das direkte Platzieren der Beschriftungen in der Karte aus Platzgründen nicht möglich ist oder die Lesbarkeit stark beeinträchtigt. Stattdessen platziert man die Beschreibung am Rand der Grafik und verbindet Ort und Beschriftung mit einem Pfeil. Es handelt sich hierbei um ein Beschriftungsproblem, das sich mit Fragestellungen des Graphenzeichnens überschneidet:

Gegeben sind n Punkte in einem Rechteck R und ebenso viele uniforme Beschriftungsrechtecke am linken und/oder rechten Rand von R. Punkte und Rechtecke werden über Pfeile verbunden und zwar so, dass die Zuordnung für den Betrachter leicht zu verstehen ist. Aus diesem Grund dürfen sich die Pfeile nicht schneiden und es werde nur gleichartige Pfeile verwendet, die aus einem horizontalen Segment und potenziell aus einem vertikalen (oder diagonalen) Segment bestehen.

Die folgende Abbildung zeigt eine mögliche Beschriftung der Regionen Frankreichs, die mit unserem Algorithmus berechnet wurde. Dabei wird einerseits die Gesamtlänge der Pfeile minimiert und andererseits die Anzahl der vorhandenen Knicke.

Der Algorithmus wurde als Java-Applet implementiert und kann mit eigenen Hintergrundgrafiken getestet werden.

In Zusammenarbeit mit a) Michael Bekos, Michael Kaufmann und Antonios Symnvonis und mit b) Herman Haverkort und Moritz Kroll.

1. Michael A. Bekos, Michael Kaufmann, Martin Nöllenburg, and Antonios Symvonis. Boundary labeling with octilinear leaders. In Proc. 11th Scandinavian Workshop on Algorithm Theory (SWAT'08), 2008. To appear. [ bib ]
2. Marc Benkert, Herman Haverkort, Moritz Kroll, and Martin Nöllenburg. Algorithms for multi-criteria one-sided boundary labeling. In Proc. 15th Int. Symp. Graph Drawing (GD '07), 2007. To appear. [ bib ]
3. Marc Benkert and Martin Nöllenburg. Improved algorithms for length-minimal one-sided boundary labeling. In Proc. 23rd European Workshop on Computational Geometry (EWCG'07), pages 190-193, Graz, Austria, 2007. [ bib | pdf ]
4. Michael A. Bekos, Michael Kaufmann, Antonios Symvonis, and Alexander Wolff. Boundary labeling: Models and efficient algorithms for rectangular maps. Computational Geometry: Theory and Applications, 36(3):215-236, 2007. [ bib | html | pdf | abstract ]
5. Michael A. Bekos, Michael Kaufmann, Antonios Symvonis, and Alexander Wolff. Boundary labeling: Models and efficient algorithms for rectangular maps. In János Pach, editor, Proc. 12th Internat. Sympos. Graph Drawing (GD'04), volume 3383 of Lecture Notes in Computer Science, pages 49-59. Springer-Verlag, 2005. [ bib | html | pdf | abstract ]