I'm Gephi main dev. Supporting DOT file format is in our roadmap and will be done very soon.
(I'm already working on a similar project. Feel free to shoot me an email at the address in my profile if you want to talk about it.)
Makes neat print-style pictures - for example this chart: http://www.texample.net/tikz/examples/gajski-kuhn-y-chart/ , which is not a graph; but the ones in the book looked good.
P.S. http://www.texample.net/tikz/examples/prims-algorithm/ illustrates the graph algorithm with overlays.