| Graph | Graph Drawing | Drawing Directed Graphs | Drawing Undirected Graphs (2D 3D) |

About 3D Graph Drawing

Similar to the 2D graph drawing, we concentrate on drawing general undirected graphs with straight lines in three-dimensional Euclidian space.

What's the problem?

In this case, we need to find a mapping L: V->R3, to position each vertex in the Euclidian space.

How to solve the problem?

Force-directed methods ([1], [2], [3], [4])

spectral drawing methods ([5],[6])

What have we finished?

we extend our 2D algorithm to 3D graph drawing and present a fast multi-level algorithm for drawing large undirected graphs in three dimensions. The combination of the bary-centralization and variant of Fruchterman-Reingold algorithm improves the efficiency and quality. We also employ the multi-level technique, constraint-normalization and oct-tree space decomposition. Experiments suggest that our algorithm is capable of achieving nice layouts of graphs with 10,000 vertices in less than 50 seconds. Furthermore, more inherent properties of graphs can be explored by roaming the resulting layouts.

       

 

What will we do next?

Explore the methods of finding the best viewpoints([7],[8])

Related downloads

A Version about Our Algorithm: SFR3DLayout (Code Bin)

A 3D Layout File Format Converter: 3DLayout2VRML (Code Bin)

A Graph Maker for Most Common Graphs: GraphMaker (Code Bin)

An interesting program for copying the original connected graphs to create a few connected components: GraphCopier (Code Bin)

 

[1] P. Eades. A Heuristic for Graph Drawing. Congressus Numerantium, 42:149-160, 1984.
[2] R.Davidson and D. Harel. Drawing Graphs Nicely using Simulated Annealing. ACM Trans. Graphics, 15(4):301-331, 1996.
[3] T. Kamada and S. Kawai. An Algorithm for Drawing General Undirected Graphs. Information Processing Letters 31:7-15, 1989.
[4] T.M.J. Fruchterman and E.M. Reingold. Graph Drawing by Froce-Directed Placement. Software Practice & Experience, 21(11):1129-1164,1991.
[5] K. M. Hall. An r-dimensional Quadratic Placement Algorithm. Management Science 17, 219-229,1970.
[6] Yehuda Koren. On Spectral Graph Drawing. LNCS 2697, Springer Verlag, 2002.
[7] Peter Eades, Michael E. Houle, and Richard Webber. Finding the Best Viewpoints for Three-Dimensional Graph Drawings.
[8] Michael E. Houle and Richard Webber. Approximation Algorithms for Finding Best Viewpoints. S.H. Whitesides (Ed.): GD'98, LNCS 1547, pp. 210-223, 1998.