Planarity, a Flash puzzle: rearrange the vertices so that no edges cross. (Cited by Joshua Burton.)
When a solution is near, the program gets very slow, which seems backward. (Thursday: It has been changed to test only on the player’s request.)
How is the graph generated? Perhaps it starts with a Delaunay triangulation of a random set of vertices, and deletes edges until each vertex has degree 4, 3 or 2.
Silly me: when there are fewer crossings, it takes longer to establish that the game is not yet over.
Delaunay triangulation is unnecessary work: more likely it starts with a regular mesh.
a FAQ has been added.
So my guesses about generation are wrong.
Last time I looked, it said it starts with N randomly-placed lines, and puts a node at each crossing; that explains why I’ve found (so far) that there’s always a solution in which each interior node’s degree is 4.