Planarity is a puzzle computer game based on a concept by Mary Radcliffe at Western Michigan University.[1] The name comes from the term planar graph. In graph theory, a planar graph is a graph that can be embedded in a plane so that no edges intersect. In the game, the player starts out with a tangled series of connected dots, and has to untangle the web until no edges intersect.
The game was written in Flash by John Tantalo at Case Western Reserve University.[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 problem of determining if a graph is planar can be solved in linear time with a simple algorithm, and any such graph is guaranteed to have a straight-line embedding by Fáry's theorem; this makes it easy to generate solvable puzzles. Puzzles can also be solved by a computer in linear time,[6] but are not as straightforward for human players to solve. 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), and others.
Contents |
If a graph is generated from n lines, then the graph will have n choose 2 = n(n-1)/2 vertices (each line has n-1 vertices, each vertex is shared with one other line) and n(n-2) edges (each line contains n-2 edges).
The first level of Planarity is built from n=4 lines, so it has n(n-1)/2=6 vertices and n(n-2)=8 edges. Each level after is generated by one more line than the last. If a level was generated with n lines, then the next level has n more vertices and 2n-1 more edges.
Input: a list L of n 2-dimensional lines, and a labeling A from each p in L to {1...n}
This algorithm assumes lists index from 1.
In the graph, every pair of distinct lines (p, q) corresponds to exactly one vertex v, but it is much more convenient to address this vertex as a single value than a tuple. So, how do we most efficiently map (p, q) into v? The function PairIndex does this by mapping each (p, q) to some number between 1 and (n(n-1)/2) (inclusive), the range of vertices.