On the Edge Label Placement Problem

Kakoulis, Konstantinos G. and Tollis, Ioannis G. (1997) On the Edge Label Placement Problem. In: Symposium on Graph Drawing, GD '96, September 18-20, 1996, Berkeley, California, USA , pp. 241-256 (Official URL: http://dx.doi.org/10.1007/3-540-62495-3_52).

Full text not available from this repository.

Abstract

Let G(V,E) be a graph, and let f:G->R² be a one to one function that produces a layout of a graph G on the plane. We consider the problem of assigning text labels to every edge of the graph such that the quality of the labeling assignment is optimal. This problem has been first encountered in automated cartography and has been refferedto as the Line Feature Label Placement (LFLP) problem. Even though much effort has been devoted over the last 15 years in the area of automated drawing of maps, the Edge Label Placement (ELP) problem has received little attention. In this paper we investigate computational complexity issues of the ELP problem, which have been open up to the present time. Specifically we prove that the ELP problem is NP-Hard.

Item Type:Conference Paper
Additional Information:10.1007/3-540-62495-3_52
Classifications:G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.630 Labeling
ID Code:148

Repository Staff Only: item control page

References

J. Ahn and H. Freeman, a program for automatic name placement. Cartographica, 21(2&3), Summer & Autumn, 1994.

J. Christensen, J. Marks, and S. Shieber. An empirical study of algorithms for Point Feature Label Placement. ACM Trans. on Graphics, 14(3):203-232, July 1995.

G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Algorithms for drawing graphs: An annotated bibliography. Comput. Geom. Theory Appl., 4: 235-282, 1994.

J.S. Doerschler and H. Freeman. A rule based system for dense map name placement. Communications of ACM, 35(1):68-79, January 1992.

L.R. Ebinger and A.M. Goulete. Noninteractive automated names placement for the 1990 decennial census. Cartography and Geographic Information systems, 17(1): 69-78, January 1990.

M. forman, F. Wagner. A packing problem with applications to lettering of maps. Proc. of 7th Annual Symp. on Comp. Geom., pages 281-288, 1991.

H. Freeman. An Expert System for the automatic placement of names on a geographical map. Information Science, 45:367-378, 1988.

H. Freeman and J. Ahn. On the problem of placing names in a geographical map. International Journal of pattern recognition and Artifical Intelligence, 1(1):121-140, 1987.

M.R. Garey and D.S. Johnson. Computers and Itractability: A Guide to hte theory of NP-Completeness. W.H. Freeman and company, NY, 1979.

E. Imhof. Positioning names of maps. The american cartographer, 2(2): 128-144,1975.

T. Kato and H. Imai. The NP-completeness of the character placement problem of 2 or 3 degrees of freedom. Record of Joint Conference of Electrical and Electronic Engineers in Kyushu, 1138, 1988. In Japanese.

J. Marks. Private Communication, 1996.

J. Marks, S. Shieber. The computational complexity of cartographic label placement. Technical Report 05-91, Harvard University, 1991.

J.W. van Roessel. An algorithm for locating candidate labeling boxes within a polygon. The american cartographer, 16(3):201-209, 1989.

P. Yoeli. The logic of automated map lettering. The Cartogrphic Journal, 9(2):99-108, December 1972.

S. Zoraster. The solution of large 0-1 integer programming problems encountered in automated cartography. O'peration Research, 38(5):752-759, September-October 1990.