I would love to find some more information how he is visualizing that stuff. Despite the "To give you some idea of algorithmic complexity, the renderings included on this page took less than a second to layout."this seems to me not hard coded but based on some visualization tool?

I think these graphs would benefit from using hierarchical bundling:

http://www.win.tue.nl/~dholten/papers/bundles_infovis.pdf