An Algorithm for the Map Labeling Problem with Two Kinds of Priorities

We consider the problem of placing labels of the points
on a plane. For each point, its position, the size of its label and a
priority are given. Moreover, several candidates of its label positions
are prespecified, and each of such label positions is assigned a
priority. The objective of our problem is to maximize the total sum
of priorities of placed labels and their points. By refining a labeling
algorithm that can use these priorities, we propose a new heuristic
algorithm which is more suitable for treating the assigned priorities.

• Noboru Abe
• Yoshinori Amai
• Toshinori Nakatake
• Sumio Masuda
• Kazuaki Yamaguchi

• Map labeling
• greedy algorithm
• heuristic algorithm
• priority.

[1] A. Wolff, The Map-Labeling Bibliography,
http://i11www.ira.uka.de/map-labeling/bibliography/.
[2] F. Wagner and A. Wolff, "A combinatorial framework for map labeling
problem,” Proc. 6th Int’l Symp. Graph Drawing (GD’98), Lecture Notes
in Computer Sciences, Volume.1547, pp.316-331, Springer, Berlin, 1998.
[3] F. Wagner, A. Wolff, V. Kapoor and T. Strijk, "Three rules suffice for good
label placement,” Algorithmica, Volume 30, No.2, pp.334-349, 2001.
[4] K. Funakawa, N. Abe, K. Yamaguchi and S. Masuda, "Algorithms for
the map labeling problem with priorities” (in Japanese), IEICE Trans.
Fundamentals, Volume J88-A, No.5, pp.677-681, 2005.
[5] N. Abe, M. Kusaki, S. Masuda and K. Yamaguchi, "An algorithm for
placing labels of the points and chains on a map,” International Journal
of Information Science and Computer Mathematics, Volume 4, Issue 2,
pp.79-99, 2011.