It's a force-directed approach: springs for edges, pairwise node-node repulsions, optional node-edge repulsion. Exterior penalty method to either handle constraints (e.g., draw the graph on a sphere) or even for "unconstrained" layout (e.g., treat the 2-d drawing problem as a 3-d drawing problem with the constraint z=0). Some other features too: check out www.cs.cmu.edu/~quixote to get all the details.

As for non-planar graphs, it doesn't give edges crossings any special treatment. Worked on that problem earlier, and concluded that it just doesn't lend itself to a force-directed approach, since I could find no way to meaningfully smooth out the discontinuities in the objective function of what consitutes a good drawing.

Never worried explicitly about drawing scale-free graphs. Would think they'd lend themselves to radial layouts, with radius reflecting graph-theoretical centrality and degree (these should be correlated) and the main optimization problem being to ordering the nodes of similar radius around their corresponding circle--a variant of the level-based approach to drawing directed acyclic graphs.

I'll confess I've been out of the field for a few years; would be curious to hear about any interesting recent results.

Honestly, I don't understand how it managed to get so much press. The original layout algorithm was terrible--so jittery that they had to market this is a feature, calling the drawings "kinetic". What's there now isn't offensive and might even have some value for wordsmiths, but I don't see why the mainstream press thought this was such a major accomplishment. Curious to hear different opinions.