This week, I started working on the Rocs graph layout capabilities. The Fruchtermani-Reingold [1] algorithm seems to be the most common option for drawing graphs automatically when no extra information about the graph is known. In fact, the Boost library implementation of this algorithm is currently being used by Rocs. However, the Fruchtermani-Reingold algorithm has some parameters that can change its results deeply. In order to better understand the algorithm and how different parameterizations lead to different results, I wrote my own C++ implementation directly in the Rocs’ libgraphtheory. This allowed me to generate debug information during the execution of the algorithm.

Unfortunately, tuning the parameters directly into the implementation is time consuming. Automatic parameter tuning solutions can not be applied in a trivial way, because the quality of the result obtained for a given parameterization is quite subjective. Therefore, I decided to make my manual tuning and evaluation process more efficient by creating a user interface that will allow me to choose parameter values and apply the algorithm to the current graph. Because I am new to Qt and the way to do this is to implement a Rocs’ plugin, it is not done yet. Creating such interface was already in my plans, but I expected to do it later.

I also studied more about graph layout algorithms. In particular, the Davidson-Harel algorithm [2] seems to be an interesting option for Rocs. It consists of two building blocks. The first is a cost function that assigns a value to each graph based on aesthetic criteria, such as the number of pairs of edges that intersect and how well the vertices are spread. The second is a Simulated Annealing optimization algorithm implementation aimed to minimize the mentioned cost function. Although the algorithm is slower than Fruchtermani-Reingold, the results seems to be quite nice. The application of this algorithm may be reserved to small graphs in order to avoid very long computation times. The exact upper bound on the size of the graph is still to be determined experimentally. However, I believe this is going to be fast enough for graphs with a few tens of vertices, which are important use cases in education and in some research areas.

For a survey about graph layout algorithms, see [3]. Although some recent results were published after [3], the most classical algorithms are well covered.

[1] Fruchtermani and E. Reingold. Graph drawing by force-directed placement. Softw. – Pract. Exp., 21(11):1129–1164, 1991

[2] R. Davidson and D. Harel. Drawing graphs nicely using simulated annealing.ACM Transactions on Graphics, 15(4):301–331, 1996.

[3] Stephen. (2012). Spring Embedders and Force Directed Graph Drawing Algorithms.