one-pass force-directed graph drawing algorithm

Question

I'm looking for a one-pass algorithm (or ideas of how to write it myself) that can calculate the two or three dimensional coordinates for a directed, unweighted graph. The only metadata the vertices have are title and category.

I need to implement this algorithm in a way that vertices can be added/removed without recalculating the entire graph structure.

This algorithm has to be applied to a large (5gb) dataset which is constantly changing.

My Google skills have led me to n-pass algorithms which are not what what I am looking for.

Answer 1

There is a related question here:

https://cstheory.stackexchange.com/questions/11889/an-algorithm-to-efficiently-draw-a-extremely-large-graph-in-real-time

The top answer has a number of papers that might be of interest. I think one of the keys to the problem is to try and recompute the location of a reduced amount of nodes in your graph.

Answer 2

I guess your question might still be an open issue. I know a research project called Tulip (http://tulip.labri.fr/TulipDrupal/) which is a (large-scale) graph viewer. A paper on the method is available at http://dept-info.labri.fr/~auber/documents/publi/auberChapterTulipGDSBook.pdf and surely you can find more algorithms browsing the personal web page of D. Auber and his colleagues.