Planarity
Encyclopedia
Planarity is a puzzle computer game based on a concept by Mary Radcliffe at Western Michigan University
. 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
. 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.
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, 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.
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.
This algorithm assumes lists index from 1.
Definition:If 1 <= p < q <= n, then PairIndex(p, q) = (p(2n-p-1)/2)+p-q, where n is the number of lines.
Claim: PairIndex is a bijection (i.e., one-to-one and onto) between {(p, q) | 1 <= p < q <= n} and {1...n(n-1)/2} for a fixed n.
Proof: Observe that PairIndex is linear in q when p is fixed. When p=1, PairIndex takes on the values {1..n-1}. When p=n-1, PairIndex is n(n-1)/2. For a given p, the minimum value is PairIndex(p,n) and the maximum value is PairIndex(p,p+1). Basic algebraic manipulation is required to show that the maximum value of PairIndex for any p is exactly one less than the minimum value for p+1. Therefore every value in {1...n(n-1)/2} must correspond to exactly one pair (p, q). ∎
Alternate definition: If 0 <= p < q < n, then PairIndex(p, q) = (p(2n-p-1)/2)+q-p.
Western Michigan University
Western Michigan University is a public university located in Kalamazoo, Michigan, United States. The university was established in 1903 by Dwight B. Waldo, and as of the Fall 2010 semester, its enrollment is 25,045....
. The name comes from the term planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
. In graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, 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
Adobe Flash
Adobe Flash is a multimedia platform used to add animation, video, and interactivity to web pages. Flash is frequently used for advertisements, games and flash animations for broadcast...
by John Tantalo at Case Western Reserve University
Case Western Reserve University
Case Western Reserve University is a private research university located in Cleveland, Ohio, USA...
. 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+
GTK+
GTK+ is a cross-platform widget toolkit for creating graphical user interfaces. It is licensed under the terms of the GNU LGPL, allowing both free and proprietary software to use it. It is one of the most popular toolkits for the X Window System, along with Qt.The name GTK+ originates from GTK;...
version by Xiph.org's Chris Montgomery
Chris Montgomery
Christopher “Monty” Montgomery is the creator of the Ogg Free Software container format and Vorbis audio codec and others, and the founder of The Xiph Foundation which promotes public domain multimedia Codecs...
, which possesses additional level generation algorithms and the ability to manipulate multiple nodes at once.
The problem of determining if a graph is planar
Planarity testing
In graph theory, the planarity testing problem asks whether, given a graph, that graph is a planar graph . This is a well-studied problem in computer science for which many practical algorithms have emerged, many taking advantage of novel data structures...
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
Fáry's theorem
In mathematics, Fáry's theorem states that any simple planar graph can be drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as curves instead of as straight line segments does not allow a larger class of graphs to be drawn...
; this makes it easy to generate solvable puzzles. Puzzles can also be solved by a computer in linear time, but are not as straightforward for human players to solve. In the field of computational geometry
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
, 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.
Algorithm
- Generate a set of random lines in a plane such that no two lines are parallel.
- 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.
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.
Pseudocode
Input: a list L of n 2-dimensional lines, and a labeling A from each p in L to {1...n}- Let G be an empty graph.
- Add vertices {1...n(n-1)/2} to G.
- For each line p in L:
- Let M be the lines q in L ordered by the intersection points of p with q and p != q.
- For each consecutive pair Mi and Mi+1:
- Let u = PairIndex(A(p), A(Mi), n).
- Let v = PairIndex(A(p), A(Mi+1), n).
- Add an edge (u, v) to G.
- Return G.
This algorithm assumes lists index from 1.
Pair Index
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.Definition:If 1 <= p < q <= n, then PairIndex(p, q) = (p(2n-p-1)/2)+p-q, where n is the number of lines.
Claim: PairIndex is a bijection (i.e., one-to-one and onto) between {(p, q) | 1 <= p < q <= n} and {1...n(n-1)/2} for a fixed n.
Proof: Observe that PairIndex is linear in q when p is fixed. When p=1, PairIndex takes on the values {1..n-1}. When p=n-1, PairIndex is n(n-1)/2. For a given p, the minimum value is PairIndex(p,n) and the maximum value is PairIndex(p,p+1). Basic algebraic manipulation is required to show that the maximum value of PairIndex for any p is exactly one less than the minimum value for p+1. Therefore every value in {1...n(n-1)/2} must correspond to exactly one pair (p, q). ∎
- This proof is due to Mary Radcliffe.
Alternate definition: If 0 <= p < q < n, then PairIndex(p, q) = (p(2n-p-1)/2)+q-p.
- This definition is practical when you index sequences from zero.
External links
- Planarity.net — the original Flash game
- JPlanarity — a simple planarity Java version
- Canvas Planarity — Planarity implemented in HTML5
- NetLogo System — Included as sample program (game) in NetLogo system