creators_name: Bekos, Michael A.
creators_name: Kaufmann, Michael
creators_name: Symvonis, Antonios
creators_name: Wolff, Alexander
editors_name: Pach, János
editors_id: Pach, János
type: confpaper
datestamp: 2005-07-19
lastmod: 2008-09-18 11:08:53
metadata_visibility: show
title: Boundary Labeling: Models and Efficient Algorithms for Rectangular Maps
ispublished: pub
subjects: G.630
subjects: P.600.700
full_text_status: none
abstract: 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).
date: 2004
date_type: published
publisher: Springer
pagerange: 49-59
refereed: FALSE
referencetext: 1. P. K. Agarwal, A. Effrat, and M. Sharir. Vertical decomposing of shallow levels in 3-dimensional arrangements and its applications. In Proc. 11th ACM Symp. Comp. Geom. (SoCG'95), pages 39-50, 1995.
2. M. A. Bekos, M. Kaufmann, A. Symvonis, and A. Wolff. Boundary labeling: Models and efficient algorithms for rectangular maps. Technical Report 2004-15, Fakultät für Informatik, Universität Karlsrughe, 2004. Available at http:/www.ubka. uni-karlsruhe.de/cgi-bin/psview?documnet=/ira/2004/15.
3.B. Chazelle and 36 co-authors. The computational geometry impact task force report. In B. Chazelle, J. E. Goodman, and R. Pollack, editors, Advances in Discrete and Computational Geometry, vol. 223, pp. 407-463. AMS 1999.
4. J.-D. Fekete and C. Plaisant. Excentric labeling: Dynamic neighborhood labeling for data visualization. In Proc. Conference on Human Factors in Computer Systems (CHI'99), pages 512-519, 1999.ACM New York.
5. M. Formann and F. Wagner. A packing problem with applications to lettering of maps. In Proc. 7th ACM Symp. Comp. Geom. (SoCG'91), pages 281-288, 1991.
6. H. Freeman, S. Marrinan, and H. Chitalia. Automated labeling of soil survey maps. In Proc. ASPRS-ACM Annual Convention, Baltimore, vol. 1, pp. 51-59, 1996.
7. M. R. Garey and D. S. Johnson. Computers and Intractability: A Giúide to the Theory of NP-Completeness. W. H. Freeman, New York, NY, 1979.
8. J. Hershberger and S. Suri. Applications of a semi-dynamic convex hull algorithm. BIT, 32:249-267, 1992.
9. C. Iturriaga. Map Labeling Problems. PhD thesis, University of Waterloo, 1999.
10. C. Iturriaga and A. Lubiw. Elastic labels around the perimeter of a map. Journal of Algorithms, 47(1):14-39, 2003.
11. G. W. Klau and P. Mutzel. Automatic layout and labelling of state diagrams. In W. Jäger and H.-J. Krebs, editors, Mathematics - Key Technology for the Future, pages 584-608. Springer-Verlag, Berlin, 2003.
12. T. Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. B. G. Teubner, 1990.
13. P. M. Vaidya. Geometry helps in matching. SIAM J. Comput., 18:1201-1225, 1989.
14. A. Wolff and T. Strijk. The Map-Labeling Bibliography. http://111www.ira.uka.de/map-labeling/bibliography/, 1996.
15. S. Zoraster. Practical results using simulated annealing for point feature label placement. Cartography and GIS, 24(4):228-238, 1997.

citation: Bekos, Michael A. and Kaufmann, Michael and Symvonis, Antonios and Wolff, Alexander (2004) Boundary Labeling: Models and Efficient Algorithms for Rectangular Maps. [Conference Paper]