Boundary Labeling

For providing information about the objects in an illustration (map, technical drawing, photo, …) one usually annotates them by a short textual description. For several reasons it might be undesirable to place these object labels inside the illustration, e.g., for lack of space or unacceptable image occlusions.

A feasible alternative is boundary labeling, a labeling method where labels are placed on the boundary of the image and connected to their corresponding objects by simple (crossing-free) leaders. In our work we restrict the leader type to orthogonal or octilinear polylines with at most one bend. We optimize an objective function, e.g., the total leader length.

Apart from static and dynamic boundary labeling we also study combined labeling models, where both internal and external labels are allowed.

Java Applet for one-sided multi-criteria boundary labeling

Java Applet for dynamic one-sided boundary labeling

1. Michael Bekos, Michael Kaufmann, Martin Nöllenburg, and Antonios Symvonis.
   Boundary Labeling with Octilinear Leaders.
   Algorithmica, 57(3):436-461, 2010.
   Special issue of SWAT 2008
   [ html ][ pdf ]
2. Marc Benkert, Herman Haverkort, Moritz Kroll, and Martin Nöllenburg.
   Algorithms for Multi-Criteria Boundary Labeling.
   Journal of Graph Algorithms and Applications, 13(3):289-317, 2009.
   Special issue of GD 2007
   [ html ][ pdf ]

1. Andreas Gemsa, Jan-Henrik Haunert, and Martin Nöllenburg.
   Boundary-Labeling Algorithms for Panorama Images.
   In: Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 289-298. ACM Press, 2011.
   [ html ][ pdf ]
2. Martin Nöllenburg, Valentin Polishchuk, and Mikko Sysikaski.
   Dynamic One-Sided Boundary Labeling.
   In: Proceedings of the 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 310-319. ACM Press, November 2010.
   [ html ][ pdf ]
3. Maarten Löffler, and Martin Nöllenburg.
   Shooting Bricks with Orthogonal Laser Beams: A First Step towards Internal/External Map Labeling .
   In: Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG '10), pages 203-206. University of Manitoba, 2010.
   [ html ][ pdf ]
4. Marc Benkert, Herman Haverkort, Moritz Kroll, and Martin Nöllenburg.
   Algorithms for Multi-Criteria One-Sided Boundary Labeling.
   In: Proceedings of the 15th International Symposium on Graph Drawing (GD'07) volume 4875 of Lecture Notes in Computer Science, pages 243-254. Springer, January 2008.
   [ html ][ pdf ]
5. Michael Bekos, Michael Kaufmann, Martin Nöllenburg, and Antonios Symvonis.
   Boundary Labeling with Octilinear Leaders.
   In: Proceedings of the 11th Scandinavian Workshop on Algorithm Theory (SWAT'08) volume 5124 of Lecture Notes in Computer Science, pages 234-245. Springer, 2008.
   [ html ][ pdf ]