Boundary labeling deals with placing annotations for objects in an image on the boundary of that image. This problem occurs frequently in situations in which placing labels directly in the image is impossible or produces too much visual clutter. Examples are annotating maps, photos, or technical/medical illustrations. Previous algorithmic results for boundary labeling consider a single layer of labels along some or all sides of a rectangular image. If, however, the number of labels is large or the labels are too long, multiple layers of labels are needed. In this article, we study boundary labeling for panorama images, where n points in a rectangle R are to be annotated by disjoint unit-height rectangular labels placed above R in K different rows (or layers). Each point is connected to its label by a vertical leader that does not intersect any other label. We present polynomial time algorithms based on dynamic programming that either minimize the number of rows to place all n labels or maximize the number (or total weight) of labels that can be placed in K rows for a given integer K. For weighted labels, the problem is shown to be (weakly) NP-hard; in this case, we give a pseudo-polynomial algorithm to maximize the weight of the selected labels. We have implemented our algorithms; the experimental results show that solutions for realistically sized instances are computed instantaneously. We have also investigated two-sided panorama labeling, for which the labels may be placed above or below the panorama image. In this model, all of the aforementioned problems are NP-hard. For solving them, we propose mixed-integer linear program formulations.

@article{GemsaHN15,
    abstract = {Boundary labeling deals with placing annotations for objects in an image on the boundary of that image. This problem occurs frequently in situations in which placing labels directly in the image is impossible or produces too much visual clutter. Examples are annotating maps, photos, or technical/medical illustrations. Previous algorithmic results for boundary labeling consider a single layer of labels along some or all sides of a rectangular image. If, however, the number of labels is large or the labels are too long, multiple layers of labels are needed.

In this article, we study boundary labeling for panorama images, where n points in a rectangle R are to be annotated by disjoint unit-height rectangular labels placed above R in K different rows (or layers). Each point is connected to its label by a vertical leader that does not intersect any other label. We present polynomial time algorithms based on dynamic programming that either minimize the number of rows to place all n labels or maximize the number (or total weight) of labels that can be placed in K rows for a given integer K. For weighted labels, the problem is shown to be (weakly) NP-hard; in this case, we give a pseudo-polynomial algorithm to maximize the weight of the selected labels. We have implemented our algorithms; the experimental results show that solutions for realistically sized instances are computed instantaneously. We have also investigated two-sided panorama labeling, for which the labels may be placed above or below the panorama image. In this model, all of the aforementioned problems are NP-hard. For solving them, we propose mixed-integer linear program formulations.},
    author = {Gemsa, A. and Haunert, J.{-}H. and N{\"{o}}llenburg, M.},
    doi = {10.1145/2794299},
    journal = {ACM Transations on Spatial Algorithms and Systems},
    number = {1},
    pages = {1{--}30},
    title = {Multirow Boundary-Labeling Algorithms for Panorama Images},
    url = {https://doi.org/10.1145/2794299},
    volume = {1},
    year = {2015}
}

	A. Gemsa, J.-H. Haunert, and M. Nöllenburg. Multirow boundary-labeling algorithms for panorama images. ACM Transations on Spatial Algorithms and Systems, 1(1):1-30, 2015. abstract doi bibtex
	Boundary labeling deals with placing annotations for objects in an image on the boundary of that image. This problem occurs frequently in situations in which placing labels directly in the image is impossible or produces too much visual clutter. Examples are annotating maps, photos, or technical/medical illustrations. Previous algorithmic results for boundary labeling consider a single layer of labels along some or all sides of a rectangular image. If, however, the number of labels is large or the labels are too long, multiple layers of labels are needed. In this article, we study boundary labeling for panorama images, where n points in a rectangle R are to be annotated by disjoint unit-height rectangular labels placed above R in K different rows (or layers). Each point is connected to its label by a vertical leader that does not intersect any other label. We present polynomial time algorithms based on dynamic programming that either minimize the number of rows to place all n labels or maximize the number (or total weight) of labels that can be placed in K rows for a given integer K. For weighted labels, the problem is shown to be (weakly) NP-hard; in this case, we give a pseudo-polynomial algorithm to maximize the weight of the selected labels. We have implemented our algorithms; the experimental results show that solutions for realistically sized instances are computed instantaneously. We have also investigated two-sided panorama labeling, for which the labels may be placed above or below the panorama image. In this model, all of the aforementioned problems are NP-hard. For solving them, we propose mixed-integer linear program formulations. doi:10.1145/2794299 @article{GemsaHN15, abstract = {Boundary labeling deals with placing annotations for objects in an image on the boundary of that image. This problem occurs frequently in situations in which placing labels directly in the image is impossible or produces too much visual clutter. Examples are annotating maps, photos, or technical/medical illustrations. Previous algorithmic results for boundary labeling consider a single layer of labels along some or all sides of a rectangular image. If, however, the number of labels is large or the labels are too long, multiple layers of labels are needed. In this article, we study boundary labeling for panorama images, where n points in a rectangle R are to be annotated by disjoint unit-height rectangular labels placed above R in K different rows (or layers). Each point is connected to its label by a vertical leader that does not intersect any other label. We present polynomial time algorithms based on dynamic programming that either minimize the number of rows to place all n labels or maximize the number (or total weight) of labels that can be placed in K rows for a given integer K. For weighted labels, the problem is shown to be (weakly) NP-hard; in this case, we give a pseudo-polynomial algorithm to maximize the weight of the selected labels. We have implemented our algorithms; the experimental results show that solutions for realistically sized instances are computed instantaneously. We have also investigated two-sided panorama labeling, for which the labels may be placed above or below the panorama image. In this model, all of the aforementioned problems are NP-hard. For solving them, we propose mixed-integer linear program formulations.}, author = {Gemsa, A. and Haunert, J.{-}H. and N{\"{o}}llenburg, M.}, doi = {10.1145/2794299}, journal = {ACM Transations on Spatial Algorithms and Systems}, number = {1}, pages = {1{--}30}, title = {Multirow Boundary-Labeling Algorithms for Panorama Images}, url = {https://doi.org/10.1145/2794299}, volume = {1}, year = {2015} }
	A. Gemsa, B. Niedermann, and M. Nöllenburg. Label placement in road maps. In Peter Widmayer, editors, volume 9079 of Lecture Notes in Computer Science. Proceedings of the 9th Conference on Algorithms and Complexity (CIAC'15), pages 221-234. Springer, 2015. Full version available at http://arxiv.org/abs/1501.07188. bibtex
	@inproceedings{gnn-lprm-15, author = {A. Gemsa and B. Niedermann and M. N{\"o}llenburg}, booktitle = {Proceedings of the 9th Conference on Algorithms and Complexity (CIAC'15)}, editor = {Peter Widmayer}, file = {gnn-lprm-15.pdf:http\://i11www.ira.uka.de/extra/publications/gnn-lprm-15.pdf:PDF}, note = {Full version available at http://arxiv.org/abs/1501.07188.}, pages = {221--234}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {{Label Placement in Road Maps}}, url = {http://dx.doi.org/10.1007/978-3-319-18173-8_16}, volume = {9079}, year = {2015} }
	L. Barth, A. Gemsa, B. Niedermann, and M. Nöllenburg. On the readability of boundary labeling. In Emilio Di Giacomo, and Anna Lubiw, editors, Lecture Notes in Computer Science. Proceedings of the 23rd International Symposium on Graph Drawing (GD'15). Springer, 2015. bibtex
	@inproceedings{bgnn-orbl-15, author = {L. Barth and A. Gemsa and B. Niedermann and M. N{\"o}llenburg}, booktitle = {Proceedings of the 23rd International Symposium on Graph Drawing (GD'15)}, editor = {Di Giacomo, Emilio and Anna Lubiw}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {{On the Readability of Boundary Labeling }}, year = {2015} }
	J.-H. Haunert, and B. Niedermann. An algorithmic framework for labeling network maps. In Proc. 21st International Conference on Computing and Combinatorics (COCOON), pages 689-700. 2015. abstract doi bibtex
	Drawing network maps automatically comprises two challenging steps, namely laying out the map and placing non-overlapping labels. In this paper we tackle the problem of labeling an already existing network map considering the application of metro maps. We present a flexible and versatile labeling model. Despite its simplicity, we prove that it is NP-complete to label a single line of the network. For a restricted variant of that model, we introduce an efficient algorithm that optimally labels a single line. Based on that algorithm, we present a general and sophisticated workflow for multiple metro lines, which is experimentally evaluated on real-world metro maps. doi:10.1007/978-3-319-21398-9_54 @inproceedings{HaunertN15, abstract = {Drawing network maps automatically comprises two challenging steps, namely laying out the map and placing non-overlapping labels. In this paper we tackle the problem of labeling an already existing network map considering the application of metro maps. We present a flexible and versatile labeling model. Despite its simplicity, we prove that it is NP-complete to label a single line of the network. For a restricted variant of that model, we introduce an efficient algorithm that optimally labels a single line. Based on that algorithm, we present a general and sophisticated workflow for multiple metro lines, which is experimentally evaluated on real-world metro maps.}, author = {Haunert, J.{-}H. and Niedermann, B.}, booktitle = {Proc. 21st International Conference on Computing and Combinatorics (COCOON)}, doi = {10.1007/978-3-319-21398-9\_54}, pages = {689{--}700}, title = {An Algorithmic Framework for Labeling Network Maps}, url = {https://doi.org/10.1007/978-3-319-21398-9\_54}, year = {2015} }
	N. Schwartges, B. Morgan, J.-H. Haunert, and A. Wolff. Labeling streets along a route in interactive 3d maps using billboards. In Proc. 18th AGILE International Conference on Geographic Information Science, pages 269-287. 2015. doi bibtex
	doi:10.1007/978-3-319-16787-9_16 @inproceedings{SchwartgesEtAl2015, author = {Schwartges, N. and Morgan, B. and Haunert, J.-H. and Wolff, A.}, booktitle = {Proc. 18th AGILE International Conference on Geographic Information Science}, doi = {10.1007/978-3-319-16787-9\_16}, pages = {269{--}287}, title = {Labeling Streets Along a Route in Interactive 3D Maps Using Billboards}, url = {https://doi.org/10.1007/978-3-319-16787-9\_16}, year = {2015} }
	J. Sultan, G. Ben-Haim, J.-H. Haunert, and S. Dalyot. User-generated data for analyzing road-type use of cyclists. In Proc. Joint Workshop of FIG Commission 3 & Commission 7 on Crowdsourcing of Land Information. 2015. FIG Article of the Month - December 2015 bibtex
	@inproceedings{label5321, author = {Sultan, J. and Ben-Haim, G. and Haunert, J.-H. and Dalyot, S.}, booktitle = {Proc. Joint Workshop of FIG Commission 3 \& Commission 7 on Crowdsourcing of Land Information}, note = {FIG Article of the Month {--} December 2015}, title = {User-Generated Data for Analyzing Road-Type Use of Cyclists}, url = {http://www.fig.net/resources/monthly\_articles/2015/Sultan\_etal\_december\_2015.asp}, year = {2015} }