Fast Compaction for Orthogonal Drawings with Vertices of Prescribed Size

Eiglsperger, Markus and Kaufmann, Michael (2002) Fast Compaction for Orthogonal Drawings with Vertices of Prescribed Size. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001, Vienna, Austria , pp. 124-138 (Official URL: http://dx.doi.org/10.1007/3-540-45848-4_11).

Full text not available from this repository.

Abstract

In this paper, we present a new compaction algorithm which computes orthogonal drawings where the size of the vertices is given as input. This is a critical constraint for many practical applications like UML. The algorithm provides a drastic improvement on previous approaches. It has linear worst case running time and experiments show that it performs very well in practice.

Item Type:Conference Paper
Additional Information:10.1007/3-540-45848-4_11
Classifications:G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.600 Poly-line > P.600.700 Orthogonal
ID Code:492

Repository Staff Only: item control page

References

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, pages 297-310, Berlin, Springer, 1999.

T.H. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms. McGraw-Hill, 1990.

G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Graph drawing: Algorithms for the visualization of graphs. Prentice Hall, 1999.

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

M. Eiglsperger. Constraints im Kandinsky-Algorithms. Master's thesis, Universität Tübingen, 1999.

U. Fößmeier. Orthogonale Visualisierungstechnicken für Graphen, Dissertation, Tübingen, 1997 (in german language).

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.

U. Fößmeier and M. Kaufmann. Algorithms and area bounds for nonplanar orthogonal drawings. In DiBattista,ed., Symposium on Graph Drawing 97, vol. 1353 of LNCS. Springer-Verlag, 1998, pages 134-145.

K. Klein, G.W. Klau, and P. Mutzel. An experimental comparison of orthogonal compaction algorithms. In Proceedings of the 8th Symposium on Graph Drawing (GD), pages 37-51, 2000.

G.W. Klau and P. Mutzel. Quasi-orthogonal drawing of planar graphs. Technical Report MPI-I-98-1-013, Max-Planck-Institut für Informatik, Saarbrücken, Germany, 1998.

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 compaction of orthogonal grid drawings. In Integer Programming and Combinatorial Optimization (IPCO '99), vol. 1610 of LNCS, pages 304-319, 1999.

Thomas Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. John Wiley and Sons, 1990.

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

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