# Incremental drawing of large graphs

I have the following problem: I'm developing a software for data visualization where I get a graph structure and represent it in 3D space. So far, I've been using force-based algorithms to draw graphs and it worked well, until I got requirement that my software should represent very big number of vertices and edges (few millions). It would be very impractical to hold all those in memory, so I'm looking for an algorithm that will enable me to stream small portions of graph as I "walk" through the space.

However, the main problem is in showing and dynamically repositioning of vertices, since I don't have already predefined positions, and I must get them from graph.

Can you point me to some algorithms for incremental drawing and streaming of graph? (and yes, I Googled a lot :))

• Cross-posted on programmers Aug 8 '11 at 14:35
• interesting problem but its not clear what you mean by "streaming" or if you are hoping to display all vertices (which seems impossible). by "stream" do you mean "view the graph locally & move through it based on adjacent vertices"? there are some examples of apps out there that do that. one that comes to mind is at thesaurus.com where you can traverse the massive synonym graph of the english language "locally"... so it seems to me this may be more a UI design/interface problem.
– vzn
Feb 5 '12 at 19:37
• one strategy would be to look at the general trend of convergence for force-based algorithms. my suspicion, I havent seen anyone look at this, they would tend to coverge to an MST (minimum spanning tree) like structure with the "center" of the MST in the center of the display space. therefore if you compute the MST & use it as a starting pt for your vertexes & just initially place them in a nonoptimal greedy way it might be acceptable.
– vzn
Feb 5 '12 at 19:40

I would suggest using some Graph database like neo4j and have a look into the paper running large graph algorithms

Probably you do not need to stream the graph.

You can run your algorithm to displace the graph in 3d space assigning positions do all nodes and then you can combine it with a Octree for culling the nodes that will not be seen by the camera.

Navigate the camera through space and query the Octree wich nodes are visible in a given moment.

As a side optimization you can group "far" nodes in one "reference" node to guide the user and when he goes near the group it splits and show the real content of the node group

Refs:

• Thanks for your answer, eduardo. However, it is not solving my problem. I can't reposition all vertices at once, because the graph is huge and my app should be working on a modest desktop computer in real time. It would be quite easy to implement the solution if I had positions of vertices :). I must stream graph and reposition vertices as I'm moving through the space. Aug 8 '11 at 13:08