Labeling Heuristics for Orthogonal Drawings

Binucci, Carla and Didimo, Walter and Liotta, Giuseppe and Nonato, Maddalena (2002) Labeling Heuristics for Orthogonal Drawings. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001, Vienna, Austria , pp. 139-153 (Official URL: http://dx.doi.org/10.1007/3-540-45848-4_12).

Full text not available from this repository.

Abstract

This paper studies the problem of computing an orthogonal drawing of a graph with labels along the edges. Labels are not allowed to overlap with each other or with edges to which they are not assigned. The optimization goal is area minimization. We provide a unified framework that allows to easily design edge labeling heuristics. By using the framework we implemented and experimentally compared several heuristics. The best performing heuristics have been embedded in the topology-shape-metrics approach.

Item Type:Conference Paper
Additional Information:10.1007/3-540-45848-4_12
Classifications:G Algorithms and Complexity > G.630 Labeling
P Styles > P.600 Poly-line > P.600.700 Orthogonal
ID Code:507

Repository Staff Only: item control page

References

P. Bertolazzi, G. Di Battista, and W. Didimo. Computing orthogonal drawings with the minimum number of bends. IEEE Transactions on computers, 49 (8), 2000.

R. Castello, R. Milli, and I. Tollis. An algorithmic framework for visualizing statecharts. In J. Marks, editor, Proc. Graph Drawing: 8th International Symposium (GD '00), vol. 1984 of LNCS, pages 139-149. Springer, 2001.

G. Di Battista, W. Didimo, M. Patrignani, and M. Pizzonia. Orthogonal and quasi-upward drawings with vertices of arbitrary size. In J. Kratochvíl, editor, Proc. Graph Drawing: 7th International Symp. (GD '99), Lecture Notes in Comput. Sci., vol. 1731, 297-310, Berlin. Springer. 2000.

G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Graph drawing. Prentice Hall, 1999.

G. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari, and F. Vargiu. An experimental comparison of three graph drawing algorithms. Comput. Geom. Theory Appl., pages 7:303-326, 1997.

U. Dogrusoz, K.G. Kakoulis, B. Madden, and I.G. Tollis. Edge labeling in the graph layout toolkit. In S. H. Whitesides, editor, Graph Drawing (Proc. GD '98), volume 1547 of Lecture Notes Comput. Sci., pages 356-363. Springer-Verlag, 1999.

T.A. Feo and M.G.C. Resende. Greedy randomized adaptive search procedure. Journal of Global Optomization, 6:109-133, 1995.

U. Fößmeier and M. Kaufmann. Drawing high degree graphs with low bend numbers. In F. Brandenburg, editor, Symposium on Graph Drawing 95, vol. 1027 of LNCS. Springer-Verlag, 1996, pp. 254-266.

GDToolkit homepage. http://www.dia.uniroma3.it/~gdt

K.G. Kakoulis and I.G. Tollis. On the Edge Label Placement Problem. In S.C. North, editor, Proceedings of Graph Drawing '96 (Proc. GD '96), vol. 1190 of LNCS, pages 241-256, Springer-Verlag, 1997.

K.G. Kakoulis and I.G. Tollis. An algorithm for labeling edges of hierarchical drawings. In G. Di Battista, editor, Proceedings of Graph Drawing '97 (Proc. GD '97), vol. 1353 of LNCS, pages 169-180, Springer-Verlag, 1998.

K.G. Kakoulis and I.G. Tollis. On the complexity of the edge label placement problem. Comput. Geom. Theory Appl., 18:1-17, 2001.

G.W. Klau and P. Mutzel. Combining graph labeling and compaction. In J. Kratochvíl, editor, Graph Drawing Conference, volume 1731 of Lecture Notes in Computer Science, pages 27-37. Springer-Verlag, 1999.

G.W. Klau and P. Mutzel. Optimal labeling of point features in the slider model. In Proc. COCOON '00, vol. 1858 of LNCS, pages 340-350, 2000.

S. Nakano, T. Nishizeki, T. Tokuyama, and S. Watanabe. Labeling points with rectangles of various shapes. In J. Marks, editor, Proc. Graph Drawing: 8th International Symposium (GD '00), vol. 1984 of LNCS, pages 91-102. Springer, 2001.

M. Patrignani. On the complexity of orthogonal compaction. Computational Geometry: Theory and Applications, 19(1):47-67, 2001.

Tycho Strijk, and Alexander Wollf. The map labeling bibliography. http://www.math-inf.uni-greifswald.de/map-labeling/bibliography

R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16 (1987), pages 421-444.

R. Tamassia, G. Di Battista, and C. Batini. Automatic graph drawing and readability of diagrams. IEEE Transactions on Systems, Man and Cybernetics, SMC-18(1):61-79, 1988.