Alan Richardson gave a talk at StarEast 2003 based around his experiences with Graph Based Testing.
You can read the 27 page supporting paper as a pdf file here.
Some tools have new versions since the paper was written and I have stumbled across some new tools.
In the paper I mention how simple it would be to construct a spreadsheet that you can use to create the graphs and use to build extra functionality with.
Well, I thought it would be unfair to let that statement stand without proof, so I have knocked up a small spreadsheet here. Feel free to download it and change as you require. Instructions on its use can be found in the zip (196kb).
Links to the majority of graph languages, lists of graph books and links to the Graph Drawing Symposiums
Graph Drawing Tools and Related Work page has a list of tools
Graph Theory Tutorials, by Chris Caldwell
Reinhard Diestel's "Graph Theory", 2nd Edition, published by Springer, has an on-line electronic version.
Harry Robinson's model based testing site always has plenty of interesting papers