# Placing nodes in a graph in a random but readable way

I'd like to create a simple map from vertices and lines - you know, like a usual graph. A tree, to be precise.

To select the location of the next point that comes from one, I use a simple circle-equation function:

function Point_on_Circle(circle_x, circle_y)

point = { x = 0, y = 0, t = math.rad(degree) }

return point

end


The result is something like this:

That's a complete mess! What to do to make it readable? As you can see, I checked, how many ways are going from each single points, but don't have much idea, what to do with them.

The problem is that it's impossible to see individual points because their lines cross each other. I want to avoid line crossing at all, like in a usual tree.

• What part of it, specifically, are you trying to fix? The labels? How things cross over each other? The grouping? Since this is kind of a visual/artistic question, you need to be technically specific about what you want to change. – MichaelHouse Sep 25 '13 at 16:03
• The problem that there's impossible too see individual points because their lines cross each other. I want to avoid line crossing at all, like in a usual tree. – Zoltán Schmidt Sep 25 '13 at 16:11
• – MichaelHouse Sep 25 '13 at 16:23
• In general, graph layout is a hard problem, with lots of different algorithms. Only "planar" graphs can be drawn without the lines crossing each other. You might look at the force-directed graph examples from d3.js. – amitp Sep 25 '13 at 16:37
• This one may also be useful: Algorithm for spreading labels in a visually appealing and intuitive way – MichaelHouse Sep 25 '13 at 16:40

Force-directed graphs may be use to create a planar graph embedding in which there are no crossings and each individual node is a reasonable distance (depending on your definition thereof) from each of the others. However there is more to this than meets the eye.

A planar embedding is distinct from the concept of a planar graph. A planar embedding is simply one representation of a graph, which contains no edge crossings. Consider a bundle of string, with various sections tied together in a complex pattern: If you drop that bundle of string, then there may be an infinite number of ways in which it may lie, once it has fallen... each of these is a separate embedding (arrangement) of the very same graph. However, some graphs are inherently non-planar and so cannot be drawn without crossings... a planar graph is a graph which may, in some way shape or form, be embedded / drawn without crossing edges. Ascertaining whether a graph is definitely planar is hard, because the definition of a non-planar graph is one which contains the Kuratowski subgraphs K3,3 or K5 as minors (not quite the same as subgraphs), and finding / extracting these algorithmically is an incredibly complex process (c.f. Boyer-Myrvold, Fraysseix et al.).

However, as you are presumably generating this graph yourself (?), and in doing so, appear to be generating a DAG (from what I can see of your snapshot), you should never have to worry about introducing either of the dreaded Kuratowski subgraphs. That is to say that without the introduction of cycles, K3,3 and K5 cannot be formed as minors.

The simplest approach to enforcing graph planarity if you are generating the graph yourself, is as follows: Instead of trying to map an existing graph topology to a planar surface topography, instead generate the graph within a surface that is already planar, then recursively subdivide the space as necessary in order to create more space for each new node as it is constructed. Structures that immediately come to mind in this regard are:

Alternatively, you may note from the Kuratowski subgraph link above, that Boost contains an implementation of Boyer-Myrvold, if you are using C++ and don't mind adding the library.

Also, a Voronoi plane along with the use of Lloyd's algorithm will give you a similar end result to a force-repelled set of nodes, ultimately resulting in a nice, organic-looking graph compare with the 3- and 4-gon approaches.

• As far as I could get it, your solution seems to be a bit overcomplicated. maybe my mistake because I didn't mention, but the graph shown in the pic should be a simple tree. I'm kinda sure that every trees should exist a way to draw where line doesn't cross each other. There's something wrong with the angles of edges. – Zoltán Schmidt Sep 25 '13 at 19:55