Abstract
We investigate the label number maximisation problem (lnm): Given a set of labels Λ, each of which belongs to a point feature in the plane, the task is to find a largest subset Λ P of Λ so that each λ ∈ Λ P labels the corresponding point feature and no two labels from Λ P overlap.
Our approach is based on two so-called constraint graphs, which code horizontal and vertical positioning relations. The key idea is to link the two graphs by a set of additional constraints, thus characterising all feasible solutions of lnm. This enables us to formulate a zero-one integer linear program whose solution leads to an optimal labelling.
We can express lnm in both the discrete and the slider labelling model. The slider model allows a continuous movement of a label around its point feature, leading to a significantly higher number of labels that can be placed. To our knowledge, we present the first algorithm that computes provably optimal solutions in the slider model. First experimental results on instances created by a widely used benchmark generator indicate that the new approach is applicable in practice.
This work is partially supported by the Bundesministerium für Bildung, Wissenschaft, Forschung und Technologie (No. 03-MU7MP1-4).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
B. V. Cherkassky and A. V. Goldberg, Negative-cycle detection algorithms, Mathematical Programming 85 (1999), no. 2, 277–311.
J. Christensen, J. Marks, and S. Shieber, An empirical study of algorithms for point-feature label placement, ACM Transactions on Graphics 14 (1995), no. 3, 203–232.
ILOG, CPLEX 6.5 Reference Manual, 1999.
G. W. Klau and P. Mutzel, Combining graph labeling and compaction, Proc. 8th Internat. Symp. on Graph Drawing (GD’ 99) (Štiřýn Castle, Czech Republic) (J. Kratochvýl, ed.), LNCS, no. 1731, Springer-Verlag, 1999, pp. 27–37.
G. W. Klau and P. Mutzel, Optimal compaction of orthogonal grid drawings, Integer Programming and Combinatorial Optimization (IPCO’ 99) (Graz, Austria) (G.P. Cornuéjols, R. E. Burkard, and G. J. Woeginger, eds.), LNCS, no. 1610, Springer-Verlag, 1999, pp. 304–319.
K. Mehlhorn and S. Näher, LEDA. A platform for combinatorial and geometric computing, Cambridge University Press, 1999.
M. van Kreveld, T. Strijk, and A. Wolff, Point labeling with sliding labels, Computational Geometry: Theory and Applications 13 (1999), 21–47.
B. Verweij and K. Aardal, An optimisation algorithm for maximum independent set with applications in map labelling, Proc. 7th Europ. Symp. on Algorithms (ESA’ 99) (Prague, Czech Republic), LNCS, vol. 1643, Springer-Verlag, 1999, pp. 426–437.
A. Wolff and T. Strijk, The map labeling bibliography, http://www.math-inf.uni-greifswald.de/map-labeling/bibliography.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Klau, G.W., Mutzel, P. (2000). Optimal Labelling of Point Features in the Slider Model. In: Du, DZ., Eades, P., Estivill-Castro, V., Lin, X., Sharma, A. (eds) Computing and Combinatorics. COCOON 2000. Lecture Notes in Computer Science, vol 1858. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44968-X_34
Download citation
DOI: https://doi.org/10.1007/3-540-44968-X_34
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67787-1
Online ISBN: 978-3-540-44968-3
eBook Packages: Springer Book Archive