Momentum Curve Algorithm

Produces straight-line grid drawings in volume 4n³, where n is the number of vertices of the graph to be drawn.

Bibliography

R.F. Cohen, P. Eades, T. Lin and F. Ruskey. Three-dimensional graph drawing. Proc. GD '94, Lecture Notes in Computer Science 894, pp. 1-11, 1994.

R.F. Cohen, P. Eades, T. Lin and F. Ruskey. Three-dimensional graph drawing. Algorithmica 17, pp. 199-208, 1997.

Kolmogorov and Barzdin Algorithm

An O(n^3/2)-time algorithm, based on augmenting the graph to an Eulerian graph and on applying a variation of an algorithm by Kolmogorov and Barzdin. The algorithm produces drawings that have O(n^3/2) volume and at most 16 bends per edge.

Bibliography

Kolmogorov, A. N., and Barzdin, Y. M. Realization of nets in 3-dimensional space. Problems in Cybernetics 8, pp. 261-268, 1967.

P. Eades, C. Stirk and S. Whitesides. The Techniques of Kolmogorov and Bardzin for Three Dimensional Orthogonal Graph Drawing. TR 95-07, Dept. of Computer Science, University of Newcastle NSW, Australia, October 1995.

P. Eades, C. Stirk and S. Whitesides. The techniques of Kolmogorov and Bardzin for three dimensional orthogonal graph drawings. Inform. Process. Lett. 60, pp. 97-103, 1996.

Slices Algorithm

A linear time algorithm that draws a graph in O(n²) volume with at most 14 bends per edge. The drawing is obtained by placing all the vertices on a horizontal plane and by assigning a further horizontal plane to every edge, one slice per edge.

Bibliography

T.C. Biedl. Heuristics for 3D-Orthogonal Graph Drawing. Presented al the 4th Twente Workshop, Enschende, June 1995.

Compact Algorithm

This algorithm requires O(n^3/2) time and volume and introduces at most 7 bends per edge.

Bibliography

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

P. Eades, A. Symvonis, S. Whitesides: Three-dimensional orthogonal graph drawing algorithms. Discret. Appl. Math. 103(1-3), pp. 55-87, 2000.

Three-Bends Algorithm

A linear time algorithm that produces orthogonal grid drawings in volume 27n³. At most 3 bends per edge are introduced. Algorithm Three-Bends is based on augmenting the graph to a 6-regular graph and on a coloring technique. The implementation of 3DCube follows the description of the algorithm given in the journal version in which, by using the result by Schrijver for the coloring phase, the time complexity of algorithm Three-Bends is O(n) instead of O(n^3/2).

Bibliography

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

P. Eades, A. Symvonis, S. Whitesides: Three-dimensional orthogonal graph drawing algorithms. Discret. Appl. Math. 103(1-3), pp. 55-87, 2000.

A. Schrijver. Bipartite edge coloring in O(Δm) time. SIAM J. on Computing 28, 3, 841-846, 1998.

Interactive Algorithm

A linear time algorithm that requires at most 4.66 n³ volume and at most 3 bends per edge. It is incremental and an be extended to draw graphs with vertices of arbitrary degree. The construction starts from a first pair of adjacent vertices, and then it adds one vertex at a time with its incident edges.

Bibliography

A. Papakostas. Information Visualization: Orthogonal Drawings of Graphs. PhD. thesis, Department of Computer Science, University of Texas at Dallas, December 1996.

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.

A. Papakostas and I.G. Tollis. Incremental orthogonal graph drawing in three dimensions. Graph Drawing (Proc. GD '97), vol. 1353 of Lecture Notes Comput. Sci., Springer-Verlag, pp. 52-63, 1997.

A. Papakostas and I.G. Tollis. Algorithms for incremental orthogonal graph drawing in three dimensions. Journal of Graph Algorithms and Applications 3, 4, pp. 81-115, 1999.

Reduce Forks Algorithm

Uses the Split&Push paradigm for three-dimensional orthogonal graph drawing. No guarantees are given on the size of the drawing, the number of bends along the edges, and the computation time.

Bibliography

M. Patrignani, Visualizzazione di Diagrammi in Tre Dimensioni, Università degli Studi di Roma "La Sapienza", Tesi di Laurea in Ingegneria Elettronica, 1996, (in Italian).

G. Di Battista, M. Patrignani, F. Francesco Vargiu. A Split-and-Push Approach to 3D Orthogonal Drawing. Graph Drawing (Proc. GD '98), volume 1547 of Lecture Notes in Computer Science, pp. 87-101, Springer-Verlag, 1998.

G. Di Battista, M. Patrignani, F. Francesco Vargiu. A Split-and-Push Approach to 3D Orthogonal Drawing, Journal of Graph Algorithms and Applications, 4:3, pp. 105-133, 2000.

M. Patrignani. Visualization of Large Graphs, Doctoral Thesis. Università degli Studi di Roma "La Sapienza", Dottorato di Ricerca in Ingegneria Informatica, XIII Ciclo, 2001.