Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm attempting to lay out arbitrary graphs in as graphically pleasing a manner as possible while trying to minimise computation required (because the layout engine will be written in browser JavaScript). Obviously one convenient way is to use a force-directed algorithm. I have two additional constraints on my graphs which are making it difficult for me to know how to progress:

  1. The nodes (which are circular) have reasonably large size -- in particular, they are not points -- and nodes must not overlap. I believe that this is best handled by enforcing a minimum edge length of 2*noderadius, and by putting an edge between every pair of nodes, and only displaying the edges which correspond to actual edges in my graph. However, there may be a better way.
  2. An edge has a circular symbol at its midpoint, and these circular symbols must also not overlap. That is: edges are permitted to cross (of course; not all graphs have a planar embedding) but the midpoints of two edges must not coincide. For example, K3,3 in its compact layout (https://upload.wikimedia.org/wikipedia/commons/thumb/f/f3/Biclique_K_3_3.svg/200px-Biclique_K_3_3.svg.png) would not be suitable because many edges have their midpoints in the same place (in the centre of the diagram) and so the symbols of all but one edge would be obscured.

I did think that this constraint would be achieveable by making the "edge midpoint symbols" actually be nodes, and thus the normal way of stopping nodes overlapping would stop the edge symbols overlapping too, but if I do that then I do not know how to make the two edges from a symbol be collinear: that is, an edge A-B with a symbol in the middle should look like one line from A to B with a symbol in the centre. If I model it as A-s-B then the force-directed algorithms will not constrain A-B to be one line, and I do not want the A-B edge to "bend" in the middle.

I understand how to use a force-directed algorithm in general, and I think I can fulfil point (1) in a force-directed algorithm, but I do not know how to stop edge symbols overlapping while being force-directed. Possibly there is a way to do this, or possibly I should be using a different graph layout algorithm entirely, in which case I invite suggestions as to what that should be. I am not a mathematician by trade, so I would appreciate it if suggestions came with a little explanation :-)

The graphs are unlikely to contain more than, say, 25 nodes, so there are not huge numbers of nodes here, and therefore I am OK with (relatively) inefficient approaches :-)

share|improve this question
add comment

1 Answer

It is an iterative process, but not all iterations have to have the same edges. I am thinking you have your graph of nodes and edges, you have springs and repulsion going on to do the basic layout. You then have a second set of edges which enforce the non-overlap of nodes and midpoint symbols - this second set includes the midpoints as nodes and doesn't worry too much about bending at the midpoints. You then alternate between the first and second set of edges, probably ending on the first set so you don't get any bends in your midpoint symbols.

share|improve this answer
    
I'm not sure I follow this. If I allow edge-bending in the second set of nodes, won't I sometimes get a layout which has non-overlapping midpoints in the second set of edges (because those edges are bent) but has overlapping midpoints with the first, unbent, edge set? –  sil May 30 '13 at 11:12
    
I am not entirely sure it will work either. Do the symbols have to be in the exact middle or is A-s--B OK? –  user80155 May 30 '13 at 12:53
    
In the exact middle; that's the aesthetic balance of the thing. –  sil May 30 '13 at 13:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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