Last week, I did not manage to work as much as I should, because I was not feeling very well. Now that I am feeling better, I am trying to work more to compensate. This is the post that should have been written last week.

This week, I implemented the first version of the graph-layout-plugin for Rocs. For now, it supports only a force based graph layout algorithm, which is an adaption of the Fruchtermani-Reingold algorithm. The graph-layout-plugin can be found at Graph Document - Tools - Graph Layout. The user interface is the following.

Screenshot of the graph-layout-plugin

The user can control the magnitude of the forces acting on the nodes using these slide bars. I decided to use slide bars because I do not think the user would benefit from having the exact value of each parameter.

I used the graph-layout-plugin to generate the following layouts. All of them are for connected graphs because I still need to handle the disconnected ones.

Complete graph. Tree. Circle graph. Planar graph. Random graph.

I experimented a little in order to find default parameters that work well. In particular, the layout algorithm used requires a rectangle in which all centers of the nodes should be placed and the forces applied depend on the area of this rectangle. In order to make things simpler, I decided to go with squares.

How big should a square for a given graph be? Sincerely, I do not now. I came up with an heuristic, though. My heuristic finds a square big enough for one to be able to place a certain number of circles at positions chosen at random with uniform probability, with high probability of not having intersections between circles. Currently, I am using one circle for each vertex and for each edge. If a random algorithm can succeed at placing this many circles without getting intersection, there should be enough space in the square so the graph layout algorithm can move nodes around easily.