Improving graphviz layout

Some softwares let users tweaking layout algorithms in real-time, as long as moving nodes with the mouse. This approach may greatly help you for larger graphs.

I mostly know Gephi (disclamer: I'm a dev).

There are a number of options i know of:

• Prefuse - They have an older Java version. The newest version is in Flash and has some nice layouts. Its called Prefuse Flare. The demo page illustrates some of its layout capabilities.
• JUNG includes a number of layout options, as well as its powerful graph analysis functions. There are some examples here.
• Networkx also includes numerous layout capabilities. Some of them are listed here.

After several attempts at drawing your graph and failing to get a layout that you deem "best", you posed the question here: is there "[b]etter free software [for] drawing small-to-medium graphs." The sole criterion you've given for evaluating layout algorithms is how closely they come to the "[s]ingle best way to represent that diagram." "Best" of course, left for you to decide.

This is more or less the same as attempting to solve a problem using a given programming language, failing, and then asking for a better programming language.

At the heart of graph drawing algorithms are optimization routines that generate then evaluation solutions ('solution' here refers to the coordinates for each node which together comprise a layout). Those solutions are evaluated according to minimization of a single criterion or a series of ranked criteria--i.e., the minimization of one or more attributes of the graph--for instance, the total number of edges that cross, or the sum of the distances between nodes (or the combination of both, or some weighted combination of those two), or the closeness to a symmetrical configuration. Graphviz is comprised of six different layout algorithms (dot neato, fdp, sfdp, twopi, and circo). Of these, it appears you only used dot; however, twopi and circo might have been better options given their strict symmetry constraints which appear to match your own idea of a correctly drawn graph.

Second, the text of your question is directed to "graphs" and graph-drawing, After reading your full description, i don't think your question has anything to do with either concept.

Beyond the general graph drawing algorithms (like graphviz), there are a number of domain-specific layout algorithms, for instance, Hasse diagrams (to represent partially ordered sets in order theory), Barabasi-Albert graphs (scale-free networks), and Erdos-Renyi (random graphs). Each of those algorithms produces a graph layout based on criteria and constraints supplied by the domain--this ought to indicate to you that there is not a single "best" layout across all domains. Although you used the term "graph" in your question, your description indicates that your problem relates to drawing state machines--a highly idiosyncratic type of graph. General graph drawing algorithms are often poor at drawing specialized graphs of this sort because the algorithm knows nothing about domain. In fact, I'm not aware of any layout algorithm for state diagrams--just like there isn't one for flow diagrams (not the same, but similar). Workflow-wise, you might draw the graph in graphviz then import it to Omnigraffle for fine tuning--in Omnigraffle, you'll have fine-grained control over the node and edge placements.