Jordi Comas at Bucknell University just mentioned this cool application on the SOCNET social network analysis discussion email list and I think it is worth a repeat: here is a great game that challenges you to find arrangements of nodes to minimize all edge crossings.
http://www.aeriagames.com/games/mini/puzzle/4467/Untangle_1.2
Not a bad way to spend a few moments appreciating the challenges of optimally laying out a graph!
