NetworkX is an amazing network graphics library where you can create images of graphs and trees.
I would look again at Graphviz, from my limited experience, the default output is not everything is so beautiful, but with a little work you can style it to look much better.
Another option is Gephi - I have never used it, but it works on Linux.
source share