An Algorithm for Labeling Edges of Hierarchical Drawings

Kakoulis, Konstantinos G. and Tollis, Ioannis G. (1998) An Algorithm for Labeling Edges of Hierarchical Drawings. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997, Rome, Italy , pp. 169-180 (Official URL: http://dx.doi.org/10.1007/3-540-63938-1_60).

Full text not available from this repository.

Abstract

Let G(V,E) be a graph, and let T be a drawing of G on the plane. We consider the problem of assigning text labels to every edge of G such that quality of the label assignment is optimal. This problem has been first encountred in automated cartography. 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) problems remains essentially unsolved. In this paper we investigate the ELP problem. We present an algorithm for the ELP problem more suitable for hierarchical drawings of graphs, but it can be adopted to many different drawing styles and still remain effective. Also, we present experimental results of our algorithm that indicate its effectiveness.

Item Type:Conference Paper
Additional Information:10.1007/3-540-63938-1_60
Classifications:G Algorithms and Complexity > G.630 Labeling
P Styles > P.480 Layered
ID Code:77

Repository Staff Only: item control page

References

J. Ahn and H. Freeman. A programm for automatic name placement. Cartographica, 21 (5&3):101-109, Summer & Autumn 1984.

C. Berge: Two theorems in graph theory. In Proc. Natl. Acad. Sci., 43, pages 842-844, 1957.

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.

G. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari, and F. Vargiu. An experimental comparison of four graph drawing algorithms. Comput. Geom. Theory Appl., 1996. to appear.

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.

ACM Computational Geometry Impact Task Force. Application challenges to computational geometry. Technical Report TR-521-96, Princeton Univ., 1996.

M. Formann and F. Wagner. A packing problem with applications to lettering of maps. In Proc. 7th Annu. ACM Sympos. Comput. Geom., pages 281-288, 1991.

A.V. Goldberg and R. Kennedy. An Efficient Cost Scaling Algorithm for the Assignment Problem. Mathematical Programming, 71:153-178, December 1995.

S.A. Hirsch. An algorithm for automatic name placement around point data. The American Cartographer, 9(1):5-17, 1982.

E. Imhof. Positioning names on maps, The American Cartographer, 2(2):128-144, 1975.

K.G. Kakoulis and I.G. Tollis. On the Edge Label Placement Problem. In S. North, editor, Graph Drawing (Proc. GD '96), volume 1190 of Lecture Notes in Computer Science, pages 241-256. Springer-Verlag, 1997.

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

J. Marks. Personal communication, 1996.

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

R.E. Tarjan. Data Structures and Network Algorithms, volume 44 of CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial Applied Mathematics. Society for Industrial Applied Mathematics, 1983.

I.G. Tollis, Graph Drawing and Information Visualization. ACM Computing Surveys, 28A(4), 1996.

F. Wagner and A. Wolff. Map labeling heuristics: Provably good and practically useful. In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages 109-118, 1995.

P. Yoeli. The logic of automated map lettering. The Cartographic Journal, 9(2):99-108, 12 1975.

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