The prefuse visualization toolkit is pretty nice, but for Java. I was wondering if there was something similar for python. My primary interest is being able to navigate dynamic graphs.
Note that prefuse now has the flare package which uses flash.
Connect that to a Python backend via web2py and you've got a great web app (just an idea).
If you're using a Mac, check out NodeBox. One extension it offers is a graph library that looks pretty good. Poke around in the NodeBox gallery some to find something similar to your problem and it should have some helpful links.
You might want to check out SUMMON, a visualization system that uses python but handles fairly large data sets. There's an impressive video of visualizing and navigating a massive tree. (Can't post the link because I'm a first time poster. It's on the SUMMON front page.)
This is well after OP, but just in case:
pydot. Allows generation & rendering of graphs. If you need graph algorithms (transitive closure etc.) also look at pygraphlib which extends and integrates pydot.
Note that neither allows interactive editing of the rendered diagram. They both use graphviz to generate output.