gifs aren't necessarily a problem. If I create my gifs with a licensed program (i.e. photoshop) then I am legal. But, if I am generating them with a non-licensed progam I am infringing. So, yes if it is easy for graphviz to gen pngs that is better, but do make it easy to change (i.e. parameter)
I do think that png would be better, but not all browser support them and another problem is (I think) no transparent background support.
