Have fun with this delightful game! It can be quite addictive!
Once you've got the hang of it, also try the little buttons at the bottom, and figure out what they do.
Also read the notes below the game!
There are some firewall policies imposed by Information and Technology Services
at Rhodes. These prevent this site from being properly viewed in some situations.
Your browser security settings or your Flash installation may also prevent the
game from loading, so try another web browser.
If this doesn't work, you can play the game at
http://planarity.net/game.html
Instructions: arrange the vertices such that no edges overlap.
Take note of these Computational Thinking elements of Planarity.
Solving this problem has an important real-world application. When engineers create a circuit or a computer chip, they have to figure out how to best lay out the components so that the necessary connections can be joined without having those connections cross over each other.
A graph is a collection of nodes (vertices) and lines (edges), where each edge connects two vertices. This is a different meaning for the other kinds of graphs that you learned at school, and draw in a Spreadsheet.
Not all graphs can be embedded in a plane (i.e. drawn on a piece of paper, without any lines crossing). Graphs that can be drawn on a plane without any lines crossing are called planar.
So this program only generates random graphs that are solvable. One of the most simple graphs that cannot be planarized has just 6 nodes: 3 houses, and 3 utility supply substations for electricity, water and gas. It is impossible to connect each house to each utility without getting at least one line crossing another. (You can even curve or squiggle your lines - it cannot be done!) See the diagram of some planar and non-planar graphs at http://en.wikipedia.org/wiki/Planar_graph
Some problems are really difficult to solve, but once you have a solution, the solution is very easy to check. One particular family of problems which are "hard-to-solve / easy-to-check" are called the NP Complete problems. Finding a planarization of a graph (what this game asks you to do) is one of these.
Although there are algorithms for solving this problem, they're difficult, and take too long to calculate. In cases like this we often look for some "rules of thumb" that will "probably" help get you closer to a solution. (The technical name for a rule of thumb is a "heuristic".) What step-by-step advice would you give a friend who wanted to know how you approached untangling these graphs?
There is an interesting relationship between the level of the game, and the the number of nodes in the graph that is generated. So at level 1, we always get 6 nodes. Level 2 gives 10 nodes ... (and you can count the others yourself.) Find a formula to calculate how many nodes a puzzle at level N will have.
Go back and count the edges of the graph at different levels. Find a formula to calculate how many nodes a puzzle at level N will have.
This game is popular on the internet. Check out thesee two videos of people solving really tough planarity problems:
Solving level 19. What is really interesting here is his algorithm. He leaves the "unhandled" nodes in the outer ring. Then he builds a "necklace" of nodes on the next innermost ring, and then another ring inside that, etc.