Planarity is a 2005 puzzle computer game by John Tantalo, based on a concept by Mary Radcliffe at Western Michigan University. The name comes from the concept of planar graphs in graph theory; these are graphs that can be embedded in the Euclidean plane so that no edges intersect. 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. In the planarity game, the player is presented with a circular layout of a planar graph, with all the vertices placed on a single circle and with many crossings. 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.
History and versions The game was written in Flash by John Tantalo at Case Western Reserve University in 2005. Online popularity and the local notoriety he gained placed Tantalo as one of Cleveland's most interesting people for 2006. 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.
Puzzle generation algorithm 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:
Generate a set of random lines in a plane such that no two lines are parallel and no three lines meet in a single point. Calculate the intersections of every line pair. Create a graph with a vertex for each intersection and an edge for each line segment connecting two intersections (the arrangement of the lines). If a graph is generated from L {\displaystyle L} lines, then the graph will have exactly ( L 2 ) = L ( L − 1 ) 2 {\displaystyle {\tbinom {L}{2}}={\tfrac {L(L-1)}{2}}} vertices (each line has L − 1 {\displaystyle L-1} vertices, and each vertex is shared with one other line) and L ( L − 2 ) {\displaystyle L(L-2)} edges (each line contains L − 2 {\displaystyle L-2} edges). The first level of Planarity is built with L = 4 {\displaystyle L=4} lines, so it has L ( L − 1 ) / 2 = 6 {\displaystyle L(L-1)/2=6} vertices and L ( L − 2 ) = 8 {\displaystyle L(L-2)=8} edges. Each level after is generated by one more line than the last. If a level was generated with L {\displaystyle L} lines, then the next level has L {\displaystyle L} more vertices and 2 L − 1 {\displaystyle 2L-1} more edges. The best known algorithms from computational geometry for constructing the graphs of line arrangements solve the problem in O ( L 2 ) {\displaystyle O(L^{2})} time, linear in the size of the graph to be constructed, but they are somewhat complex. Alternatively and more simply, it is possible to index each crossing point by the pair of lines that cross at that point, sort the crossings along each line by their x {\displaystyle x} -coordinates, and use this sorted ordering to generate the edges of the planar graph, in near-optimal O ( L 2 log L ) {\displaystyle O(L^{2}\log L)} time. Once the vertices and edges of the graph have been generated, they may be placed evenly around a circle using a random permutation.
… excerpt ends here. Continue reading the full article.
