If you guys go into that, I'd suggest leaving a path open for TikZ (text to embed pics in TeX, see here http://news.ycombinator.com/item?id=1204172 , about use in a graph theory book).

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.