Since you'd need the graph layouted already anyway, I'm wondering what Mapnik would bring. Nice label placement along paths is about the only thing I can think of right now. Or tiled rendering maybe, but there should be easier ways for that, too.
Tiled rendering is what I'm most interested in, but I'm not aware of any easier way to go about it. The alternative would be to code something from scratch... But my graphs look so much like the road network I'm inclined to leverage what's out there already.
I'd like to render complex graphs with Mapnik, as I do for OSM (which is just a graph after all).