Boundary Labeling: Models and Efficient Algorithms for Rectangular Maps

Bekos, Michael A. and Kaufmann, Michael and Symvonis, Antonios and Wolff, Alexander (2004) Boundary Labeling: Models and Efficient Algorithms for Rectangular Maps. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004 , pp. 49-59(Official URL:

Full text not available from this repository.


In this paper, we present boundary labeling, a new approach for labeling point sets with large labels. We first place disjoint labels around an axis-parallel rectangle that contains the points. Then we connect each label to its point such that no two connections intersect. Such an approach is common e.g. in technical drawings and medical atlases, but so far the problem has not been studied in the literature. The new problem is interesting in that it is a mixture of a label-placement and a graph-drawing problem. This work has partially been supported by the DFG grants Ka 512/8-2 and WO 758/4-1, by the German-Greek cooperation program GRC 01/048 and the EPEAEK program Pythagoras 89181(28).

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-31843-9_7
Classifications: G Algorithms and Complexity > G.630 Labeling
P Styles > P.600 Poly-line > P.600.700 Orthogonal

Actions (login required)

View Item View Item