Fun, challenging, (addictive!) game
This is the coolest online game I’ve seen in a LONG time. Warning: suitable mainly for nerds.
This makes a puzzle game out of graph theory. A graph is just a bunch of points and a bunch of lines between the points. A graph is called planar if you can draw it on a piece of paper so that none of the lines cross each other (except at the points). If you’re still confused about what this means, go to the game and play around with the points. The graph that you start out with probably won’t be planar.
A graph is uniquely determined by how many points it has and which points are connected. But there are plenty of different-looking ways to draw a graph on paper. This is the point of the game — you’re given a graph which is planar, but it’s not drawn in a planar fashion. You’re supposed to rearrange the points so that it is planar.
I do wonder about the computational complexity of the game. My strategy right now is to move each vertex near to the other ones it’s connected to, and after I’ve done that with a number of the vertices, I can kind of visualize the graph as a planar graph that is folded over itself a few times, and then I just have to “unfold” it. I’ve gotten up to level 37 using this strategy.
However, I don’t think that strategy is the mathematically optimal one. It just makes sense considering the way I process information visually. I bet that one could write an algorithm to solve this problem in O(nlog(n)) “moves” (a “move” is a geometric move of a single point). Maybe even O(n). I think when I don’t make mistakes, my algorithm is about O(nlog(n)) moves. But the total complexity of the algorithm might be much higher — geometric problems are typically not very easy. I’m not really sure how you would program an algorithm to solve this (I certainly wouldn’t be able to code up my technique!); I am fairly sure that any strategy that always reduces the number of crossings on each step will not always work.
Any ideas?
