Automatically rotate a graph

Question

I'm drawing graphs with force-directed layout, and the problem is that the created graphs are oriented randomly and unpredictably, which makes looking at them somewhat confusing. For example, suppose node A is a member of the two separate graphs G1 and G2. With force-directed layout, node A may end up on the left side of G1, but on the right side of G2.

Now I'm trying to reduce the confusion by automatically rotating the graph in a deterministic way after the graph layout algorithm has been applied to it. One could compute the minimum bounding rectangle for this, but it would be nicer if the rotation algorithm could include some of the additional information on the vertices and edges.

In this case, each vertex is a document with a timestamp and a word count, and the edges represent undirected and directed relationships between the documents. Perhaps there's a way to rotate the graph so that older documents concentrate on the left, and newer ones on the right? Same with links: The arrows should point more to the right than to the left. This sounds like a reasonable approach, but I have no idea how to calculate something like this (and Google didn't really help either).

Notes:

• I think there are graph layout algorithms that take care of the rotation, but I'd prefer a solution that involves force-directed layout.
• One could let the user rotate the graph by hand, but this requires saving the graph orientation, which is something I'd prefer to avoid, cause there's no room for this in the document database.

Answer 1

You can either use

• a dynamic force-directed algorithm that preserves a user's mental map between frames (e.g. Graph Drawing in Motion, in Journal of Graph Algorithms and Applications (JGAA), 6(3), 353–-370, 2002), or
• Procrustes Analysis to translate, rotate and scale frames so that the relative positions of "landmarks points" are preserved.

Answer 2

You may use a layout which uses a seed to generate random numbers. Try the Yifan Hu multilevel algorithm in Gephi.