A Pairing Technique for Area-Efficient Orthogonal Drawings

Papakostas, Achilleas and Tollis, Ioannis G. (1997) A Pairing Technique for Area-Efficient Orthogonal Drawings. In: Symposium on Graph Drawing, GD '96, September 18-20, 1996, Berkeley, California, USA , pp. 355-370 (Official URL: http://dx.doi.org/10.1007/3-540-62495-3_60).

Full text not available from this repository.


An orthogonal drawing of a graph is a drawing such that vertices are placed on grid points and edges are drawn as sequences of vertical and horizontal segments. In this paper we present linear time algorithms that produce orthogonal drawings of graphs with n nodes. If the maximum degree is four, then the drawing produced by our first algorithm needs area not greater than 0.76n², and introduces no more than 2n+2 bends. Also, every edge of such a drawing has at most two bends. Our algorithm is based on forming and placing pairs of vertices of the graph. If the maximum degree is three, then the drawing produced by our second algorithm needs at most 0.25n² area, and at most \lfloor 0.5n+2l+1 \rfloor bends (\lfloor 0.5n \rfloor +3 bends, if the graph isbiconnected), where l is the number of biconnected components that are leaves in th block tree. For biconnected graphs, this algorithm produces optimal drawings with respect to the number of bends (within a constant of two), since there is a lower bound of 0.5n+1 in the number of bends for orthogonal drawings of degree 3 graphs.

Item Type:Conference Paper
Additional Information:10.1007/3-540-62495-3_60
Classifications: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:109

Repository Staff Only: item control page


Therese Biedl. Embedding Nonplanar Graphs in the Rectangular Grid. Rutcor Research Report 27-93, 1993.

Therese Biedl. New Lower Bounds for Orthogonal Graph Drawings. Proc. of GD '95, LNCS, 1027, Springer-Verlag, 1995, pages 28-39.

T. Biedl and G. Kant. A Better Heuristic for Orthogonal Graph Drawings. Technical Report, Utrecht Univ., Dept. of Comp. Sci., UU-CS-1995-04. Prelim. version appeared in Proc. 2nd Ann. European Symposium on Algorithms (ESA '94), LNCS, 855, pages 24-35, Springer-Verlag, 1994.

G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Algorithms for drawing graphs: An annotated bibliography. Comput. Geom. Theory Appl., 4: 235-282, 1994. Also available via anonymous ftp from ftp.cs.brown.edu, gdbiblio.tex.Z and gdbiblio.ps.Z in /pub/papers/compgeo.

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. The version of the paper with the four algorithms can be obtained from http://www.cs.brown/people/rt.

G. Di Battista, G. Liotta, and F. Vargiu. Spirality of orthogonal representations and optimal drawings of series-parallel graphs and 3-planar graphs. Proc. Workshop on Algorithms and Data Structures, LNCS, 709, Springer-Verlag, 1993, pages 151-162.

S. Even and G. Garnot. Rectilinear Planar Drawings with Few Bends in Each Edge. Tech. Report 797, Comp. Sci. Dept., Technion, Israel Inst. of Tech., 1994.

S. Even and R.E. Tarjan. Computing an st-numbering. Theoretical Computer Science, 2:339-344, 1976.

A. Garg and R. Tamassia. On the Computational Complexity of Upward and Rectilinear Planarity Testing. Proc. DIMACS Workshop GD '94, LNCS, 894, Springer-Verlag, pages 286-297, 1994.

Goos Kant. Drawing planar graphs using the lmc-ordering. Proc. 33th Ann. IEEE Symp. on Found. Of Comp. Sci., pages 101-110, 1992.

F.T. Leighton. New lower bound techniques for VLSI. Proc. 22nd Ann. IEEE Symp. on Found. Of Comp. Sci., pages 1-12, 1981.

C.E. Leiserson. Area-Efficient Graph Layouts (for VLSI). Proc. 21st Ann. IEEE Symp. on Found. Of Comp. Sci., pages 270-281, 1980.

A. Papakostas and I.G. Tollis. Algorithms for Area-Efficient Orthogonal Drawings. Tech. Report UTDCS-06-95, The University of Texas at Dallas, 1995. Also available on the WWW at http://wwwpub.utdallas.edu/~tollis.

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

A. Papakostas and I.G. Tollis. Issues in Interactive Orthogonal Graph Drawing. Proc. of GD '95, LNCS, 1027, Springer-Verlag, pages 419-430, 1995.

Markus Schäffter. Drawing Graphs on Rectangular Grids. Discr. Appl. Math. 63 (1995), pages 75-89.

J. Storer. On minimal node-cost planar embeddings. Network 14 (1984), pages 181-212.

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. Planar grid embeddings in linear time. IEEE Trans. Circuits Syst., CAS-36(9):1230-1234, 1989.

R. Tamassia, I. Tollis, and J. Vitter. Lower Bounds for Planar Orthogonal Drawings of Graphs. Information Processing Letters 39 (1991), pages 35-40.

L. Valiant. University Considerations in VLSI Circuits", IEEE Trans. on Comp., vol. C-30, no 2, (1981), pages 135-140.