Planarity
Planarity is a 2005
History and versions
The game was written in
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 lines, then the graph will have exactly vertices (each line has vertices, and each vertex is shared with one other line) and edges (each line contains edges). The first level of Planarity is built with lines, so it has vertices and edges. Each level after is generated by one more line than the last. If a level was generated with lines, then the next level has more vertices and more edges.
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. 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 -coordinates, and use this sorted ordering to generate the edges of the planar graph, in near-optimal time. Once the vertices and edges of the graph have been generated, they may be placed evenly around a circle using a random permutation.
Related theoretical research
The problem of
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 of the input vertices fixed in place at their original positions, for a constant that has not been determined precisely but lies between 1/4 and slightly less than 1/2. When the planar graph to be untangled is a
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.
References
- PCWorld, archived from the originalon 2009-06-04
- ^ Massie, Laura (2005-06-20). "Case student develops booming on-line game". Case Western Reserve University News Center. Retrieved 2007-09-30.
- ^ Castro, Laura (2005-11-18). "Case student one of Cleveland's "Most Interesting People"". The Observer. Archived from the original on September 8, 2006. Retrieved 2007-09-30.
- ^ "Most Interesting People 2006" (Press release). Cleveland Magazine. January 2006. Retrieved 2015-05-19.
- ^ "gPlanarity home".
- MR 1394503
- MR 1075065
- MR 3277216
- MR 2412266
- MR 3213195
External links
- Planarity.net — the original Flash game
- NetLogo System — Included as sample program (game) in NetLogo system
- Planarity — Version using SVG and the d3 JavaScriptlibrary
- Multitouch Planarity — Multiplayer- and multitouch-enabled version written in Python using libavg.