How can I make DOT/neato graphs more compact without introducing overlap?

Question

My question is essentially the same as this one but the given answer doesn't work for me.

Here is a sample rendering (source) with

compound=true;
overlap=scalexy;
splines=true;
layout=neato;

There is some unnecessary overlap in the edges but this isn't too bad, the main problem is all the wasted space.

I tried setting sep=-0.7; and here's what happens.

The spacing is much better but now there is some overlap with the nodes. I experimented with different overlap parameters and this is the only one which gives remotely acceptable results.

I tried changing to fdp layout and setting the spring constant attribute K globally but I just got stuff like this:

The source is all straightforward a--b--c sort of stuff, no fancy tricks.

What I want is for all edges to be shortened as much as possible (up to a minimum) provided that this adjustment doesn't introduce any new overlaps, which is where sep fails completely. That doesn't seem like it should be too hard for a layout engine to do. Is it possible with the graphviz suite? I don't mind changing rendering software, but I don't want to annotate the source on a per-node or per-edge basis.

My ideal result would be to minimize the deviation in edge length, considered one node at a time, i.e. each node would have edges of equal length apart from the necessary exceptions, but that's wishful thinking. The priority is to reduce the length of each edge with the constraint that this cannot introduce overlap.

I will accept partial solutions but they must be fully automatic and open source.

How can I do this? Thanks.

Answer 1

I found https://sites.google.com/site/kuabus/programming-by-hu/graphviz-test-tool, an interactive tool for parameterizing the many options and repeatedly rendering them. I went through the full list provided by the Java application, eventually ending up with this set of attributes:

overlap=false
maxiter=99999999
damping=9999999
voro_margin=.001
start=0.1
K=1
nodesep=999999999999
labelloc=c
defaultdist=9999999
size=20,20
sep=+1
normalize=99999999
labeljust=l
outputorder=nodesfirst
concentrate=true
mindist=2
fontsize=99999999
center=true
scale=.01
inputscale=99999999
levelsgap=9999999
epsilon=0.0001

I was not able to find a parameterization of neato that made producing the desired "moderately scaled" graph possible.

Answer 2

You should set

overlap = compress;

this should compress it at much as possible. Try sep = +1; first, and then play with values between 0 and +1 to find the optimal setting for you.