A friend sent me this link to a flash game called planarity. I’ve been trying to figure out a way to solve the figures besides trial and error. Are there math solutions to this sort of problem?
This represents a rather famous problem known as graph planarity. There are solutions known, but nothing that’s practically usable on any large system.
A linear (in the number of edges and nodes) time algorithm was worked out by Hopcroft and Tarjan over 30 years ago. The planarity testing part is still quite nice but the embedding algorithm is a bit messy. Several people have come up with simpler forms. For lots of links, Google on:
Hopcroft Tarjan planarity
Note that the best known algorithms for higher genus surfaces get more complex quickly. While polynomial for a fixed genus, the degree of the polynomial depends on the genus. There are still some open problems in Complexity Theory regarding genus and NP-Completeness.
By just screwing around (I’m on level 8 right now), it seems to me that the algorithm should start by finding the verticies with lowest number of connecting edges (2 is the minimum), and complete any 3 vertices with common edges first and isolate them (as triangles), then move on to 4 vertices with 3 common edges, etc. I know I’m missing alot here for an algorithm, but my method seems to work most of the time and I’m too addicted to the damn thing to follow ftg’s link.
Thanks, YR, that does help some. The only other rule I’ve found is to move anything that has all the links on the other side over to that side.
I was under the impression that planarity testing was NP-complete. Am I misremembering, or is the some restriction on that algorithm that prevents it from solving the general case?
Geez, level 5 took me 5 minutes. I’m not sure I’ll even make it to level 8.
The flash application doesn’t need to do any sort of planarity testing if it’s built right. It can just first build up a random planar graph and then rearrange all the vertices to make it non planar. Building planar graphs should be at most O(n^2).
I found this game through this “games blog” and there has been a lot of discussion of tips and strategies in the comments section for this game.
BTW, if you’ve been waiting a long time for it to finish figuring out whether you’ve won or not, the game designer apparently intends to streamline that algorithm somehow in the near future.
Planarity testing is certainly not NP. A rather crude O(n^2) algorithm would just be for every set of lines, test whether they intersect.
Checking whether a graph is planar is also not NP, you just need to check for K(3,3) and K(5) subgraphs*.
Converting a non-planar graph to a planar graph may very well be NP.
- A K(3,3) graph is when you have nodes A, B, C, D, E, F and links AD, AE, AF, BD, BE, BF, CD, CE, CF
A K(5) graph is when you have nodes A, B, C, D, E and all nodes are linked to all other nodes.
If a graph does not contain either of these subgraphs, it can be planarised.
Type the following into Google:
Hopcroft Tarjan planarity
This makes no sense.
It terms of charactization this is true but is it practically useless as a basis for an algorithm. It would be like using Cramer’s rule to find matrix inverses. Good Math, lousy Computer Science.
“Converting”? If you mean adding new nodes at edge crossings it’s trivial. If you mean finding the minimum number of edges to remove to make it planar, that’s NP-Hard.
Thanks for the links! I will try some of the strategies in the comments.
I have noticed that they are not all equally hard–sometimes I can get to 8 fairly quickly, and sometimes I can’t get past 6.
Yes, I did that. It was a simple question, you know–how long could it’ve taken you to answer it?
That was becoming an issue when I finished level 9. Then I had to leave “work” for the day so I couldn’t go on… 
I somehow found this puzzle therapeutic, kinda like unraveling knots which I am also good at.
Perhaps I’m using somewhat different definitions here, but I don’t think that intersection is a graph-theory concept. A graph is a set of connections between vertices. The puzzles presented by that Flash game are from the start and remain planar graphs. What the player is doing is just trying to find a planar representation of them, which is not the same thing.
Yeah, but the edges are represented as lines. If we can check that each line doesn’t intersect with another, then we can show that the correct representation has been found.
Finished level 14. At that point every other move has lag associated with it and my browser suggested killing the slow script a dozen or so times during the last game. At that point it is not worth continuing.
Sorry, graph theory is not my specialty and I’m not familiar with the terminology. From now on, I’ll use the term planar for an abstract graph that can be drawn with no intersecting lines and planar representation for the actual drawing of a graph in XY space with no intersecting lines.
Testing for a planar representation is an O(n^2) algorithm at worst.
Yes, there are probably more efficient algorithms but this was the one I was taught in 1st year. My point is that it establishes an upper bound on complexity which is far from NP.
I meant converting a planar graph from a non-planar representation to a planar representation, ie: What you are meant to do in that game. AFAIK, this is still an active area of research and no P algorithms have yet been found to do it consistently. There are quite a few heuristics to bring the typical case down to something reasonable but worst case is still NP AFAIK.
Please read my first post. The Hopcroft-Tarjan linear time planarity algorithm is an extremely famous graph algorithm and is one of the key reasons they were awarded the Turing Award.