Graph drawing by high-dimensional embedding (2004) [pdf]

I used this technique in a javascript application to render large graphs (>200k nodes). On my laptop, with my simple implementation, it could lay out a graph of that size in about 5-10 seconds (running in firefox 20-something I think). Given the amount of time required for getting a force-directed layout, this algorithm literally saved the whole project.

The layout it produces strongly emphasizes hierarchy, at least in my implementation. While it's not as pretty as a real force-directed layout for the type of data I was rendering, it's quite passable visually.