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)

degree = math.random(rad_min, rad_max)

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

point.x = circle_x + radius*math.cos(point.t)
point.y = circle_y + radius*math.sin(point.t)

return point

end

The result is something like this: enter image description here

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.

up vote 3 down vote accepted

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.