I've made some tests on the force based layout, and it seems it has really a complexity in nlog(n) (and we cannot do really better).

Thus when you take 3 seconds to compute a layout with 100 nodes, then it's normal to take 40 seconds with 1000 nodes.

Regards

Mathieu