Turn-Regularity and Planar Orthogonal Drawings (Extended Abstract)

Bridgeman, Stina and Di Battista, Giuseppe and Didimo, Walter and Liotta, Giuseppe and Tamassia, Roberto and Vismara, Luca (1999) Turn-Regularity and Planar Orthogonal Drawings (Extended Abstract). In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999, Štirín Castle, Czech Republic , pp. 8-26 (Official URL: http://dx.doi.org/10.1007/3-540-46648-7_2).

Full text not available from this repository.

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 minimum area and minimum total edge length within that area can be computed in O(n^{7/4} log 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.

Item Type:Conference Paper
Additional Information:10.1007/3-540-46648-7_2
Classifications:G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.540 Planar
ID Code:234

Repository Staff Only: item control page

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-334. 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. Brandenburg, 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, 1988.

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, 1988.

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.

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. Symp. 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.

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.