Two Algorithms for Three Dimensional Orthogonal Graph Drawing

Eades, Peter and Symvonis, Antonios and Whitesides, Sue (1997) Two Algorithms for Three Dimensional Orthogonal Graph Drawing. In: Symposium on Graph Drawing, GD '96, September 18-20, 1996, Berkeley, California, USA , pp. 139-154 (Official URL: http://dx.doi.org/10.1007/3-540-62495-3_44).

Full text not available from this repository.

Abstract

We use basic results from graph theory to design two algorithms for constructing 3-dimesional, intersection-free orthogonal grid drawings of n vertex graphs of maximum degree 6. Our first algorithm gives drawings bounded by an O(\sqrt(n)) \times O(\sqrt(n)) \times O(\sqrt(n)) box; each edge route containing at most 7 bends. The best previous result generated edge routes containing up to 16 bends per route. Our second algorithm gives drawings having at most 3 bends per edge route. The drawings lie in an O(n) \times O(n) \times O(n) bounding box. Together , the two algorithms initiate the study of bends/bounding box trade-off issues for 3-dimensional grid drawings.

Item Type:Conference Paper
Additional Information:10.1007/3-540-62495-3_44
Classifications:G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.060 3D
ID Code:117

Repository Staff Only: item control page

References

C. Berge. Graphs and Hypergraphs. North Holland, Amsterdam, 1973.

S. Bhatt, S. Cosmadakis. The Complexity of Minimizing Wire Lengths in VLSI Layouts. Inform. Proc. Lett., vol. 25, 1987, pages 263-267.

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

T. Biedl and G. Kant. A Better Heuristic for Orthogonal Graph Drawings. Proc. 2nd Ann. European Symposium on Algorithms (ESA '94), LNCS, 855, pages 24-35, Springer-Verlag, 1994.

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

J.A. Bondy and U.S.R. Murty. Graph Theory with Applications. North-Holland, Amsterdam, 1976.

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.

D. Dolev, F.T. Leighton, H. Trickey. Planar Embeddings of Planar Graphs. Advances in Computing Research 2 (ed. F.P. Preparata), JAI Press Inc., Greenwich, CT, USA, 1984, pages 147-161.

P. Eades, C. Stirck, S. whitesides. The Techniques of Kolmogorov and Barzdin for Three Dimensional Orthogonal Graph Drawing. TR 95-07, Dept. of Comp. Sci., University of Newcastle, Australia, October 1995.

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

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.

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.

P. Hall. On representation of subsets. J. London Mathematical Society, vol. 10, pages 26-30, 1935.

J.E. Hopcroft, R.M. Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput., vol. 2(4), 1973, pages 225-231.

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

A.N. Kolmogorov and Ya.M. Brazdin. About realisation of sets in 3-dimensional space. Problems in Cybernetics. March 1967, pages 261-268.

A. Papakostas and I.G. Tollis. A Pairing Technique for Area-Efficient Orthogonal Drawings. these proceedings.

Franco P. Preparata. Optimal three-dimensional VLSI layouts. Mathematical Systems Theorie, vol. 16, 1983, pages 1-8.

A.L. Rosenberg. Three-Dimensional Integrated Circuity. Advanced Research in VLSI (eds. Kung, Sproule, Steele), pages 69-80, 1981.

A.L. Rosenberg. Three-Dimensional VLSI: A case Study. Journal of the ACM, vol. 30(3), pages 397-416, 1983.

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

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. A unified approach to visibility representations of planar graphs. Discrete Comput. Geom., 1(4):321-341, 1986.

R. Tamassia and I.G. Tollis. Efficient Embeddings of Planar Graphs in Linear Time. IEEE Symp. on Circuits and Systems, pages 495-498, 1987.

R. Tamassia and I.G. Tollis. Planar grid embeddings in linear time. IEEE Trans. Circuits Syst., CAS-36(9):1230-1234, 1989.

David Wood. On Higher-Dimensional Orthogonal Graph Drawing. Manuscript, 1996, Dept. of Comp. Sci., Monash U.