# Graph layout algorithm with extra “nodes” on edges, and with non-point nodes

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

-