Abstract
Given an orthogonal representation H with n vertices and bends, we study the problem of computing a planar orthogonal drawing of H with small area. This problem has direct applications to the development of practical graph drawing techniques for information visualization and VLSI layout. In this paper, we introduce the concept of turn-regularity of an orthogonal representation H, provide combinatorial characterizations of it, and show that if H is turn-regular (i.e., all its faces are turn-regular), then a planar orthogonal drawing of H with minimum area can be computed in O(n) time, and a planar orthogonal drawing of H with minimum area and minimum total edge length within that area can be computed in O(n 7=4log n) time. We also apply our theoretical results to the design and implementation of new practical heuristic methods for constructing planar orthogonal drawings. An experimental study conducted on a test suite of orthogonal representations of randomly generated biconnected 4-planar graphs shows that the percentage of turn-regular faces is quite high and that our heuristic drawing methods perform better than previous ones.
Research supported in part by the Consiglio Nazionale delle Ricerche under Project “Geometria Computazionale Robusta con Applicazioni alla Grafica ed al CAD”, by the National Science Foundation under grants CCR-9732327 and CDA-9703080, and by the U.S. Army Research Office under grant DAAH04-96-1-0013.
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
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, Algorithms and Data Structures (Proc. WADS’ 97), volume 1272 of Lecture Notes Comput. Sci., pages 331–344. Springer-Verlag, 1997.
P. Bertolazzi, G. Di Battista, G. Liotta, and C. Mannino. Upward drawings of triconnected digraphs. Algorithmica, 6(12):476–497, 1994.
T. C. Biedl. New lower bounds for orthogonal graph drawings. In F. J. Bran-denburg, editor, Graph Drawing (Proc. GD’ 95), volume 1027 of Lecture Notes Comput. Sci., pages 28–39. Springer-Verlag, 1996.
T. C. Biedl and G. Kant. A better heuristic for orthogonal graph drawings. Comput. Geom. Theory Appl., 9(3):159–180, 1998.
J. A. Bondy and U. S. R. Murty. Graph Theory with Applications. North-Holland, Amsterdam, The Netherlands, 1976.
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(5-6):303–325, 1997.
G. Di Battista and G. Liotta. Upward planarity checking: “Faces are more than polygons”. In S. H. Whitesides, editor, Graph Drawing (Proc. GD’ 98), volume 1547 of Lecture Notes Comput. Sci., pages 72–86. Springer-Verlag, 1998.
G. Di Battista, G. Liotta, and F. Vargiu. Spirality and optimal orthogonal drawings. SIAM J. Comput., 27(6):1764–1811, 1998.
G. Di Battista and R. Tamassia. Algorithms for plane representations of acyclic digraphs. Theoret. Comput. Sci.,61(2,3):175–198, 1988.
W. Didimo and G. Liotta. Computing orthogonal drawings in a variable embedding setting. In K.-Y. Chwa and O. H. Ibarra, editors, Algorithms and Computation (Proc. ISAAC’ 98), volume 1533 of Lecture Notes Comput. Sci., pages 79–88. Springer-Verlag, 1998.
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.
A. Garg and R. Tamassia. Planar drawings and angular resolution: Algorithms and bounds. In J. van Leeuwen, editor, Algorithms (Proc. ESA’ 94), volume 855 of Lecture Notes Comput. Sci., pages 12–23. Springer-Verlag, 1994. 26 S.S. Bridgeman et al.
A. Garg and R. Tamassia. On the computational complexity of upward and rectilinear planarity testing. In R. Tamassia and I. G. Tollis, editors, Graph Drawing (Proc. GD’ 94), volume 894 of Lecture Notes Comput. Sci., pages 286–297. Springer-Verlag, 1995.
A. Garg and R. Tamassia. A new minimum cost flow algorithm with applications to graph drawing. In S. North, editor, Graph Drawing (Proc. GD’ 96), volume 1190 of Lecture Notes Comput. Sci., pages 201–216. Springer-Verlag, 1997.
N. Gelfand and R. Tamassia. Algorithmic patterns for orthogonal graph drawing. In S. H. Whitesides, editor, Graph Drawing (Proc. GD’ 98), volume 1547 of Lecture Notes Comput. Sci., pages 138–152. Springer-Verlag, 1998.
F. Harary. Graph Theory. Addison-Wesley, Reading, MA, 1969.
F. Hoffmann and K. Kriegel. Embedding rectilinear graphs in linear time. Inform. Process. Lett., 29(2):75–79, 1988.
M. Y. Hsueh and D. O. Pederson. Computer-aided layout of lsi circuit building-blocks. In Proc. IEEE Internat. Symp. Circuits and Systems, 1979.
G. W. Klau and P. Mutzel. Optimal compaction of orthogonal grid drawings. In G. Cornuejols, R. E. Burkard, and G. J. Woeginger, editors, Integer Programming and Combinatorial Optimization (Proc. IPCO’ 99), volume 1610 of Lecture Notes Comput. Sci., pages 304–319. Springer-Verlag, 1999.
T. Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. B. G. Teubner-John Wiley & Sons, Stuttgart, Germany-Chichester, England, 1990.
R. H. J. M. Otten and J. G. van Wijk. Graph representations in interactive layout design. In Proc. IEEE Internat. Sympos. Circuits and Systems, pages 914–918, 1978.
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.
M. Patrignani. On the complexity of orthogonal compaction. In F. Dehne, A. Gupta, J.-R. Sack, and R. Tamassia, editors, Algorithms and Data Structures (Proc. WADS’ 99), volume 1663 of Lecture Notes Comput. Sci., pages 56–61. Springer-Verlag, 1999.
J. M. Six, K. G. Kakoulis, and I. G. Tollis. Refinement of orthogonal graph drawings. In S. H. Whitesides, editor, Graph Drawing (Proc. GD’ 98), volume 1547 of Lecture Notes Comput. Sci., pages 302–315. Springer-Verlag, 1998.
L. Stockmeyer. Optimal orientation of cells in slicing floorplan design. Inform. Control, 57(2/3):91–101, 1983.
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 and I. G. Tollis. Planar grid embedding in linear time. IEEE Trans. Circuits Syst., CAS-36(9):1230–1234, 1989.
R. Tamassia, I. G. Tollis, and J. S. Vitter. Lower bounds for planar orthogonal drawings of graphs. Inform. Process. Lett., 39(1):35–40, 1991.
G. Vijayan and A. Wigderson. Rectilinear graphs and their embeddings. SIAM J. Comput., 14(2):355–372, 1985.
W. Wimer, I. Koren, and I. Cederbaum. Floorplans, planar graphs and layouts. IEEE Trans. Circuits Syst., CAS-35(3):267–278, 1988.
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
Bridgeman, S.S., Di Battista, G., Didimo, W., Liotta, G., Tamassia, R., Vismara, L. (1999). Turn-Regularity and Planar Orthogonal Drawings. 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_2
Download citation
DOI: https://doi.org/10.1007/3-540-46648-7_2
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