Orthogonal and Quasi-upward Drawings with Vertices of Prescribed Size (Extended Abstract)

Di Battista, Giuseppe and Didimo, Walter and Patrignani, Maurizio and Pizzonia, Maurizio (1999) Orthogonal and Quasi-upward Drawings with Vertices of Prescribed Size (Extended Abstract). In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999, Štirín Castle, Czech Republic , pp. 297-310 (Official URL: http://dx.doi.org/10.1007/3-540-46648-7_31).

Full text not available from this repository.

Abstract

We consider the problem of computing orthogonal drawings and quasi-upward drawings with vertices of prescribed size. For both types of drawings we present algorithms based on network flow techniques and show that the produced drawings are optimal within a wide class. Further, we present the results of an experimentation conducted on the algorithms that we propose for orthogonal drawings. The experiments show the effectiveness of the approach.

Item Type:Conference Paper
Additional Information:10.1007/3-540-46648-7_31
Classifications:P Styles > P.840 Upward
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.999 Others
ID Code:358

Repository Staff Only: item control page

References

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs, NJ, 1993.

C. Batini, E. Nardelli, and R. Tamassia. A layout algorithm for data flow diagrams. IEEE Trans. Softw. Eng., SE-12(4):538-546, 1986.

C. Batini, M. Talamo, and R. Tamassia. Computer aided layout of entity-relationship diagrams. Journal of Systems and Software, 4:163-173, 1984.

P. Bertolazzi, G. Di Battista, and W. Didimo. Computing orthogonal drawings with the minimum number of bends. In F. Dehne, A. Rau-Chaplin, J.-R. Sack, and R. Tamassia, editors, Proc. 5th Workshop Algorithms Data Struct., volume 1272 of Lecture Notes Comput. Sci., pages 331-344. Springer-Verlag, 1997.

P. Bertolazzi, G. Di Battista, and W. Didimo. Computing orthogonal drawings with the minimum number of bends. manuscript, 1998.

P. Bertolazzi, G. Di Battista, and W. Didimo. Quasi-upward planarity. In S. H. Whitesides, editor, Graph Drawing (Proc. GD '98), volume 1547 of Lecture Notes Comput. Sci., pages 15-29. Springer-Verlag, 1998.

T. Biedl and G. Kant. A better heuristic for orthogonal graph drawings. Comput. Geom. Theory Appl., 9:159-180, 1998.

T. C. Biedl. Relating bends and size in orthogonal graph drawings. Inform. Process. Lett., 65:111-115, 1998.

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.

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., 7:303-325, 1997.

S. Even. Graph Algorithms. Computer Science Press, Potomac, Maryland, 1979.

U. Fößmeier, C. Hess, and M. Kaufmann. On improving orthogonal drawings: The 4M-algorithm. In S. Whitesides, editor, Graph Drawing (Proc. GD '98), volume 1547 of Lecture Notes Comput. Sci., pages 125-137. Springer-Verlag, 1999.

U. Fößmeier and M. Kaufmann. Drawing high degree graphs with low bend numbers. In F. J. Brandenburg, editor, Graph Drawing (Proc. GD '95), volume 1027 of Lecture Notes Comput. Sci., pages 254-266. Springer-Verlag, 1996.

U. Fößmeier and M. Kaufmann. Algorithms and area bounds for nonplanar orthogonal drawings. In G. Di Battista, editor, Graph Drawing (Proc. GD '97), volume 1353 of Lecture Notes Comput. Sci., pages 134-145. Springer-Verlag, 1997.

T. Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. Wiley-Teubner, 1990.

T. Nishizeki and N. Chiba. Planar graphs: Theory and algorithms. Ann. Discrete Math., 32, 1988.

A. Papakostas and I. G. Tollis. Algorithms for area-efficient orthogonal drawings. Comput. Geom. Theory Appl., 9(1-2):83-110, 1998. Special Issue on Geometric Representations of Graphs, G. Di Battista and R. Tamassia, editors.

J. M. Six, K. G. Kakoulis, and I. G. Tollis. Refinement of orthogonal graph drawings. In S. Whitesides, editor, Graph Drawing (Proc. GD '98), volume 1547 of Lecture Notes Comput. Sci., pages 302-315. Springer-Verlag, 1999.

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

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

L. Valiant. Universality considerations in VLSI circuits, IEEE Trans. Comput., C-30(2):135-140, 1981.