For everyone interested in algorithms behind Graphviz, here's a paper so start with:
This work is absolutely amazing. I've tried implementing it a few years ago (as an excervise when preparing for Google interview). So naive. I've found out that I have read each and every sentence extremely carefully to get things right. I got quite far but never finished the implementation. (And I did not get an offer from Google either.)
I second this.
I'm using yEd a lot, and I especially like layouting functions like hierarchical layout. I often use it to plan interdependent tasks. I just start with tasks I know are required and the thing of their prerequisites. Quite fast this gives a big graph structure. Then I run a hierarchical layout on this and suddenly I have a very clear structure of tasks. Their hierarchical layouting algorithm is great. I suspect it may be based on GraphViz dot's algorithm (http://www.graphviz.org/Documentation/TSE93.pdf) as it produces results of similar high quality.
I also love the UI of yEd. Zooming in and out, creating nodes and dependencies/edges feels just great.