<p>I would suggest using some Graph database like <a href="http://neo4j.org/" rel="nofollow">neo4j</a> and have a look into the paper <a href="http://highscalability.com/blog/2010/3/30/running-large-graph-algorithms-evaluation-of-current-state-o.html" rel="nofollow">running large graph algorithms</a></p>

CC BY-SA 3.0
2011-08-08T16:24:12.493Z
2011-08-08T16:24:12.493Z
Thang Dinh
<p>Probably you do not need to stream the graph.</p>

<p>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.</p>

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

<p>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</p>

<p>Refs:</p>

<p><a href="http://en.wikipedia.org/wiki/Octree" rel="nofollow">http://en.wikipedia.org/wiki/Octree</a>
<a href="http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter37.html" rel="nofollow">http://developer.nvidia.com/GPUGems2/gpugems2_chapter37.html</a></p>

CC BY-SA 3.0
2011-08-08T13:08:22.073Z
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.
Leon Wickliff
CC BY-SA 3.0
2011-08-08T12:53:10.370Z
2011-08-08T12:53:10.370Z
eduardo
<p>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. </p>

<p>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.</p>

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

<p>Thanks in advance!</p>

CC BY-SA 3.0
2011-08-08T14:35:35.947Z
[Cross-posted on programmers](http://programmers.stackexchange.com/questions/99403/incremental-and-partial-drawing-of-the-large-graphs)
Peter Taylor
CC BY-SA 3.0
2012-02-05T19:37:19.463Z
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
CC BY-SA 3.0
2012-02-05T19:40:11.800Z
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
<graph-theory><cg.comp-geom><data-streams><graph-drawing>
Incremental drawing of large graphs
Leon Wickliff
# Incremental drawing of large graphs

(Asked by: username_0 on 2011-08-08)

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 :))

Thanks in advance!

**Tags:** graph-theory, cg.comp-geom, data-streams, graph-drawing
> **Comments:**
> **username_1**: [Cross-posted on programmers](http://programmers.stackexchange.com/questions/99403/incremental-and-partial-drawing-of-the-large-graphs)  
> **username_2**: 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.  
> **username_2**: 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.  

---

## 2 answers

### Answer by username_3 on 2011-08-08. Score: 2

I would suggest using some Graph database like [neo4j](http://neo4j.org/) and have a look into the paper [running large graph algorithms](http://highscalability.com/blog/2010/3/30/running-large-graph-algorithms-evaluation-of-current-state-o.html)


---

### Answer by username_4 on 2011-08-08. Score: 0

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:

<http://en.wikipedia.org/wiki/Octree>
[http://developer.nvidia.com/GPUGems2/gpugems2\_chapter37.html](http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter37.html)

> **Comments:**
> **username_0**: 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.  

---

