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

About 2D Graph Drawing

Graph drawing is a conventional means for visualizing the relational information and its usefulness depends on the readability of the resulting layouts. A nice drawing can convey the inherent structure of the graph exactly and intuitively. The state of the art in graph drawing is surveyed comprehensively in "Drawing Graphs: Methods and Models" (M. Kaufmann and D. Wagner).

We concentrate on drawing general undirected graphs with straight lines in two-dimensional Euclidian space.

What's the problem?

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

How to solve the problem?

Two popular heuristics to this problem are often adopted. One of them is force-directed methods ([1], [2], [3], [4]), which define a force model (or an energy function) similar to the system of springs or celestial bodies, and acquire the nice layout by minimizing the function gradually. The simplicity and flexibility of force-directed algorithms provide a solid foundation to solve the general graph drawing problems. However, the procedure of minimizing the energy function requires relatively high time complexity which is at least quadratic. For larger graphs (typically, the graphs with more than 1000 vertices), the slow converge undermines the performance severely. The other popular method ([5], [6]) is spectral drawing methods, which similarly define an energy function and minimize the function to produce nice layouts. Koren ([6]) generalizes the spectral drawing and positions vertices by the generalized eigenvectors corresponding to the minimal eigenvalue of Laplacian matrix of graphs. And also, he explains the link between the spectral drawing and bary-centralization: When the energy reaches its minimal state, the position of every vertex is equal to the weighted center of its adjacent vertices. The spectral algorithm presents a faster procedure; however, the resulting layouts are often more congested compared to force-directed methods.  

What have we finished?

We present a new multi-level algorithm for drawing general large undirected graphs, which combines the spectral method with the Fruchterman-Reingold algorithm. As far as we know, it is the first time to introduce the combination. Besides, the constraint-normalizing method and quad-tree space decomposition are employed to speed up our algorithm. The experiments show its high performance and nice results. It is extremely fast and can draw nicely 10,000 vertex graphs in around 5 seconds and 1000,000 vertex graphs in less than 10 minutes. The comparison with the results [7] also supports our conclusions. More importantly, our simple but practical speed-up techniques can be easily generalized to improve the performance of general force-directed algorithms.

What will we do next?

Generalize to the other force-directed algorithms;
Survey extensively and compare with other algorithms for drawing large graphs;

Watch an interesting video about similar topic:

Related downloads

A Version about Our Algorithm: SFR2DLayout (Code Bin)

A 2D Layout Viewer: 2DLayoutViewer (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)