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.
Research supported in part by the CNR Project “Geometria Computazionale Ro- busta con Applicazioni alla Graca ed al CAD”, and by the ESPRIT LTR Project 20244 (ALCOM-IT)
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
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.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Di Battista, G., Didimo, W., Patrignani, M., Pizzonia, M. (1999). Orthogonal and Quasi-upward Drawings with Vertices of Prescribed Size. In: Kratochvíyl, J. (eds) Graph Drawing. GD 1999. Lecture Notes in Computer Science, vol 1731. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46648-7_31
Download citation
DOI: https://doi.org/10.1007/3-540-46648-7_31
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66904-3
Online ISBN: 978-3-540-46648-2
eBook Packages: Springer Book Archive