Planarity is a 2005 puzzle computer game by John Tantalo, based on a concept by Mary Radcliffe at Western Michigan University.
By Fáry's theorem, if a graph is planar, it can be drawn without crossings so that all of its edges are straight line segments.
The goal for the player is to eliminate all of the crossings and construct a straight-line embedding of the graph by moving the vertices one by one into better positions.
The game was written in Flash by John Tantalo at Case Western Reserve University in 2005.
[2] Online popularity and the local notoriety he gained placed Tantalo as one of Cleveland's most interesting people for 2006.
[3][4] It in turn has inspired the creation of a GTK+ version by Xiph.org's Chris Montgomery, which possesses additional level generation algorithms and the ability to manipulate multiple nodes at once.
[5] The definition of the planarity puzzle does not depend on how the planar graphs in the puzzle are generated, but the original implementation uses the following algorithm: If a graph is generated from
The best known algorithms from computational geometry for constructing the graphs of line arrangements solve the problem in
time,[6] linear in the size of the graph to be constructed, but they are somewhat complex.
-coordinates, and use this sorted ordering to generate the edges of the planar graph, in near-optimal
Once the vertices and edges of the graph have been generated, they may be placed evenly around a circle using a random permutation.
The problem of determining whether a graph is planar can be solved in linear time,[7] and any such graph is guaranteed to have a straight-line embedding by Fáry's theorem, that can also be found from the planar embedding in linear time.
In the field of computational geometry, the process of moving a subset of the vertices in a graph embedding to eliminate edge crossings has been studied by Pach and Tardos (2002),[9] and others, inspired by the planarity puzzle.
[10][11][12][13] The results of these researchers shows that (in theory, assuming that the field of play is the infinite plane rather than a bounded rectangle) it is always possible to solve the puzzle while leaving
input vertices fixed in place at their original positions, for a constant
However, determining the largest number of vertices that may be left in place for a particular input puzzle (or equivalently, the smallest number of moves needed to solve the puzzle) is NP-complete.
Verbitsky (2008) has shown that the randomized circular layout used for the initial state of Planarity is nearly the worst possible in terms of its number of crossings: regardless of what planar graph is to be tangled, the expected value of the number of crossings for this layout is within a factor of three of the largest number of crossings among all layouts.
[14] In 2014, mathematician David Eppstein published a paper[15] providing an effective algorithm for solving planar graphs generated by the original Planarity game, based on the specifics of the puzzle generation algorithm.