On Improving Orthogonal Drawings: The 4M-Algorithm

Fößmeier, Ulrich and Heß, Carsten and Kaufmann, Michael (1998) On Improving Orthogonal Drawings: The 4M-Algorithm. In: Graph Drawing 6th International Symposium, GD’ 98, August 13-15, 1998, Montréal, Canada , pp. 125-137 (Official URL: http://dx.doi.org/10.1007/3-540-37623-2_10).

Full text not available from this repository.

Abstract

Orthogonal drawings of graphs are widely investigated in the literature and many algorithms have been presented to compute such drawings. Most of these algorithms lead to unpleasant drawings with many bends and a large area. We present methods how to improve the quality of given orthogonal drawings. Our algorithms try to simulate the thinking of a human spectator in order to achieve good results. We also give instructions how to implement the strategies in a way that a good runtime performance can be achieved.

Item Type:Conference Paper
Additional Information:10.1007/3-540-37623-2_10
Classifications:M Methods > M.999 Others
G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.070 Area / Edge Length
G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
ID Code:262

Repository Staff Only: item control page

References

T. Biedl and G. Kant. A Better Heuristic for Orthogonal Graph Drawings. Proc. 2nd Ann. European Symposium on Algorithms (ESA '94), LNCS, 855, pages 124-135, Springer-Verlag, 1994.

T. Biedl and M. Kaufmann. Area-efficient static and incremental graph drawings. In 5th European Symposium on Algorithms, vol. 1284 of LNCS, pages 37-52. Springer-Verlag, 1997.

T. Biedl, B. Madden, and I.G. Tollis. The three-phase method: A unified approach to orthogonal graph drawing. In DiBattista,ed., Symposium on Graph Drawing 97, vol. 1353 of LNCS. Springer-Verlag, 1998., pages 391-402.

G. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari, and F. Vargiu. An experimental comparison of three graph drawing algorithms. In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages 306-315, 1995.

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

U. Fößmeier, G. Kant, and M. Kaufmann. 2-Visibility drawings of planar graphs. In S. North,ed., Symposium on Graph Drawing 96, vol. 1190 of LNCS, Springer-Verlag, 1996, pages 155-168.

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.

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.

C. Heß. Knicksparende Strategien für orthogonale Zeichnungen. Diploma thesis, Tübingen, 1998 (in german language).

M.Y. Hsueh. Symbolic layout and compaction of integrated circuits. Ph. D. Thesis, University of california at Berkeley, 1980.

K. Mehlhorn and S. Näher. A faster compaction algorithm with automatic Jog Insertion. Proc. 5th MIT Conf. Advanced Research in VLSI, The MIT Press, 1988, 297-314.

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

P. Rosenstiehl and R.E. Tarjan. Rectilinear planar layouts and bipolar representations of planar graphs. Discr. & Comput. geom., vol. 1, no. 4, 1986, 343-353.

A. Papakostas and I.G. Tollis. Improved Algorithms and Bounds for Orthogonal Drawings. Proc. DIMACS Workshop GD '94, LNCS, 894, Springer-Verlag, pages 40-51, 1995.

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 and I.G. Tollis. A unified approach to visibility representations of planar graphs. Discrete Comput. Geom., 1(4):321-341, 1986.

R. Tamassia and I.G. Tollis. Planar grid embeddings in linear time. IEEE Trans. Circuits Syst., CAS-36(9):1230-1234, 1990.

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.

R. Tamassia and I.G. Tollis. Efficient Embeddings of Planar Graphs in Linear Time. IEEE Symp. on Circuits and Systems, pages 495-498, 1987.