It was interesting to me that the grapher Paolo pointed to last time did NOT use format-graph-from-roots. I don't know whether this was because that grapher was built before format-graph-from-roots was generally available (I think it's always been in CLIM), or because the graph layout algorithm in format-graph-from-roots is not very amenable to having the user intervene into graph layout.
It might be instructive to compare format-graph-from-roots with the grapher that appears in Garnet, which is based on a cells-like constraint architecture. In that framework there are edge objects that are constrained to be attached to points on graph nodes. I don't see how one could really build a user-modifiable graph w/o such objects. On the other hand, I'm not sure how one could introduce such entities, since CLIM doesn't necessarily easily admit for propagation cycles. I.e., such objects would only work in panes with particular sorts of display-functions.
BTW, on a dual SMP 3G with 1G of RAM last night, I tried to layout a graph with approx 5K nodes, and McCLIM went into GC thrashing and took the lisp process down (which I take to be an accomplishment). I hope to be able to have some time to run the profiler and try to figure out what might be optimized --- I haven't tweaked my compiler settings at all, so this might simply be badly-compiled iterative code eating the stack...
It's too early, and I'm probably rambling, so I'll sign off...