Incremental Orthogonal Graph Drawing in Three Dimensions

Papakostas, Achilleas and Tollis, Ioannis G. (1998) Incremental Orthogonal Graph Drawing in Three Dimensions. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997, Rome, Italy , pp. 52-63 (Official URL: http://dx.doi.org/10.1007/3-540-63938-1_50).

Full text not available from this repository.

Abstract

We present two algorithms for orthogonal graph drawing in three dimensional space. For graphs of maximum degree six, the 3-D drawing is produced in linear time, has volume at most 4.66n³ and each edge has at most three bends. If the degree of the graph is arbitrary, the vertices are represented by solid 3-D boxes whose surface is proportional to their degree. The produced drawing has two bends per edge. Both algorithms guarantee no crossings and can be used under an interactive setting (i.e., vertices arrive and enter the drawing on-line), as well.

Item Type:Conference Paper
Additional Information:10.1007/3-540-63938-1_50
Classifications:M Methods > M.300 Dynamic / Incremental / Online
G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.060 3D
ID Code:67

Repository Staff Only: item control page

References

T. Biedl and G. Kant, A Better Heuristic for Orthogonal Graph Drawings, Proc. 2nd Ann. European Symposium on Algorithms (ESA '94), Lecture Notes in Computer Science, vol. 855, pp. 24-35, Springer-Verlag, 1994.

M. Brown and M. Narjork, Algorithm animation using 3D interactive graphics, Proc. ACM Symp. on User Interface Software and Technology, 1993, pp. 93-100.

I. Bruss and A. Frick, Fast Interactive 3-D Visualization, Proc. of Workshop GD '95, Lecture Notes in Comp. Sci. 1027, Springer-Verlag, 1995, pp. 99-110.

R. Cohen, P. Eades, T. Lin, F. Ruskey, Three Dimensional Graph Drawing, Proc. of DIMACS Workshop GD '94, Lecture Notes in Comp. Sci. 894, Springer-Verlag, 1994, pp. 1-11.

I. Cruz and J. Twarog, 3D Graph Drawing with Simulated Annealing, Proc. of Workshop GD '95, Lecture Notes in Comp. Sci. 1027, Springer-Verlag, 1995, pp. 162-165.

G. Di Battista, P. Eades, R. Tamassia and I. Tollis, Algorithms for Drawing Graphs: An Annotated Bibliography, Computational Geometry: Theory an Applications, vol. 4, no.5, 1994, pp. 235-282. Also available via anonymous ftp from ftp.cs.brown.edu, gdbiblio.tex.Z and gdbiblio.ps.Z in /pub/papers/compgeo.

P. Eades, C. Stirk, S. Whitesides, The Techniques of Kolmogorov and Bardzin for Three Dimensional Orthogonal Graph Drawings, TR 95-07, Dept. of Computer Science, University of Newcastle, Australia, 1995. Also to appear in Information Processing Letters.

P. Eades, A. Symvonis, S. Whitesides, Two Algorithms for Three Dimensional Orthogonal Graph Drawing, Proc. of Workshop GD '96, Lecture Notes in Comp. Sci. 1190, Springer-Verlag, 1996, pp. 139-154.

A. Garg and R. Tamassia, GIOTTO3D: A System for Visualizing Hierarchical Structures in 3D, Proc. of Workshop GD '96, Lecture Notes in Comp. Sci. 1190, Springer-Verlag, 1996, pp. 193-200.

Goos Kant, Drawing Planar Graphs Using the Canonical Ordering, Algorithmica, vol. 16, no. 1, 1996, pp. 4-32.

A. N. Kolmogorov and Y. M. Bardzin, About Realization of Sets in 3-dimensional Space, Problems in Cybernetics, 1967, pp. 261-268.

J. MacKinley, G. Robertson, S. Card, Cone Trees: Animated 3d visualizations of hierarchical information, In Proc. of SIGCHI Conf. on Human Factors in Computing, pp. 189-194, 1991.

A. Papakostas and I. G. Tollis, Algorithms for Area-Efficient Orthogonal Drawings, Technical Report UTDCS-06-95, The University of Texas at Dallas, 1995.

A. Papakostas and I. G. Tollis, Issues in Interactive Orthogonal Graph Drawing, Proc. of Workshop GD '95, Lecture Notes in Comp. Sci. 1027, Springer-Verlag, 1995, pp. 419-430.

A. Papakostas and I. G. Tollis, A Pairing Technique for Area-Efficient Orthogonal Drawings, Proc. of Workshop GD '96, Lecture Notes in Comp. Sci. 1190, Springer-Verlag, 1996, pp. 355-370.

A. Papakostas, J. Six and I. G. Tollis, Experimental and Theoretical Results in Interactive Graph Drawing, Proc. of Workshop GD '96, Lecture Notes in Comp. Sci. 1190, Springer-Verlag, 1996, pp. 371-386.

A. Papakostas and I. G. Tollis, Incremental Orthogonal Graph Drawing in Three Dimensions, Technical Report UTDCS-02-97, The University of Texas at Dallas, 1997. (available through www.utdallas.edu/~tollis)

S. Reiss, An engine for the 3D visualization of programm information, J. Visual Languages and Computing, vol. 6, no. 3, 1995.

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

R. Tamassia and I. Tollis, Planar Grid Embeddings in Linear Time, IEEE Trans. on Circuits and Systems CAS-36 (1989) pp. 1230-1234.