Algorithm for creating tree-like network structures

Question

I'm trying to procedurally model tree-like network structures with the following properties:

• A root with variable number of nodes
• A variable depth of nodes
• When graphically laid out, edges or nodes must never intersect or overlap

I don't have a background in maths or programming, so I am not sure that I am using the correct terminology. Maybe a picture would better explain what I am after:

I know my way around Ruby pretty well, so I think I should be able to implement a basic algorithm that generates these models. Any pointers or recommendations?

Answer 1

Graph drawing is a little more directly relevant than the whole field of graph theory.

In particular, I'm a fan of force-based layout. See this demo from the D3 library for an introduction.

The basic idea is that you model the graph edges with springs or repulsors, and use a physics integration method to "resolve" the positions of all the nodes. You can do this in real-time like the previous demo, which is kind of fun but also distracting, or you can do a number of physics iterations before rendering a final static layout.

That D3 library has a large number of other layout modes to inspire you with, and being JavaScript-based is a great way to prototype or experiment with any layout algorithms you're interested in.

Answer 2

First, in order for your graph to obey the crucial property of any two edges do not cross, it must be a planar graph.

A tiny tutorial on the graph drawing topic is given here.

Using force driven layouts may not guarantee convergence to a planar graph: (for example, if a vertex is inside a face, apply an elastic spring force and push the vertex outside the face using the nearest edge normal). This approach would be interesting to animate, but it might not converge (unless it has been proven somewhere..?).

So, while I cannot reproduce here an algorithm for untangling a planar graph (or downright drawing it in its canonical form), there are plenty of resources dealing with the issue (some in linear time):

• http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.6677
• http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/sw-upg-08.pdf
• http://arxiv.org/pdf/0709.0170.pdf

NOTE: if your graph is a tree, then I suggest reading this.

RELATED: "Untangle"-Game AI

Answer 3

You could use some form of Space Colonisation.

Examples ProcWorld and Sea of Memes show growing 'real trees', but could probably be adapted for arbitrary tree structures.

Space Colonisation assumes you have some limited area to be filled by a competitive 'lifeform' which grows over one or more iterations. This competitive aspect might not fit what you're wanting to do, if you're just wanting to generate random trees/graphs with no overlap.

EDIT:

Space Colonisation has certain conditions on the growth that I think pretty much guarantee no overlapping edges (and normally you'd process the tree afterwards anyway) - but it will only help you if you don't already have a graph/tree.

So if you already have a graph, Space Colonisation will not help you - see other answers like @Sean's force-based layout. If you are generating a graph while also needing to lay it out (or can store some position information for later) - this might to what you need.