Logo

Login | Create Account

Labeling Heuristics for Orthogonal Drawings

Binucci, Carla and Didimo, Walter and Liotta, Giuseppe and Nonato, Maddalena (2002) Labeling Heuristics for Orthogonal Drawings. [Conference Paper]

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
Classifications:G Algorithms and Complexity > G.630 Labeling
P Styles > P.600 Poly-line > P.600.700 Orthogonal
ID Code:507
Deposited By:Arnopolina, Galina
Deposited On:21 Dec 2004
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2265&spage=139

Repository Staff Only: item control page

References

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

2. 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.

3. 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.

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

5. 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.

6. 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.

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

8. 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.

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

10. 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.

11. 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.

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

13. 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.

14. 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.

15. 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.

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

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

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

19. 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.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.