Automatically rotate a graph

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.

Thank you very much for the answer. Unfortunately, neither of these approaches are going to work in my case. The first one won't work because there aren't any transitions between the graphs (sometimes graph A -> graph B, but usually there's no such order). The second one won't work because procrustes rotation is based on minimizing the "procrustes distance" between two shapes --- in my case, there's only one shape.Anyway, I'll give you an upvote for the effort and the neat idea of normalizing the scale :-)

python dude 2010-08-23 13:45:42

Yes, I misread the question. Maybe you need a force-directed algorithm that incorporates directionality? e.g. Dwyer, T. and Koren, Y. and Marriott, K., Drawing Directed Graphs using Quadratic Programming, IEEE Transactions on Visualization and Computer Graphics, 12(4), 536-548 (2006) and Dwyer, T. and Koren, Y., Dig-CoLa: Directed Graph Layout through Constrained Energy Minimization, Proceedings of the IEEE Symposium on Information Visualization (InfoVis'05), IEEE Computer Society, 65-72, 2005.

Martin Harrigan 2010-08-23 15:16:20

Whoa, quadratic programming?? I didn't I'd need something this sophisticated for such a small problem ;-) But this looks like the solution to my problem, so thanks again!

python dude 2010-08-23 19:42:26

ansaurus

tags:

views:

answers:

Automatically rotate a graph

related questions