Installing graphviz on Ubuntu Lucid Lynx 10.04

If you want sfdp (a great layout for large graphs), then you need the .debs from the graphviz site (not through the ubuntu repos).

Download the develpment snapshots here
note, if you don't use the language specific bindings listed, you don't need to download those.

sudo aptitude install libdevil1c2 libgtkglext1
sudo dpkg -i graphviz_*.deb graphviz-dev*_all.deb 
graphviz-doc*_all.deb libgraphviz4_*.deb libgraphviz-dev_*.deb libgv-ruby_*.deb

Now, you can run sfdp!