Planarity

This article is about the game; for the graph theory property, see Planar graph.

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.

Algorithm

1. Generate a set of random lines in a plane such that no two lines are parallel.
2. Calculate the intersections of every line pair.
3. 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

File:Planarity-intersections-animation.gif

The labeling and each iteration of the p loop for a case of n=4.

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 M_i and M_i+1:

Let u = PairIndex(A(p), A(M_i), n).

Let v = PairIndex(A(p), A(M_i+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.

References

• Prosenjit Bose, Vida Dujmovic, Ferran Hurtado, Stefan Langerman, Pat Morin, David R. Wood (2008). "A polynomial bound for untangling geometric planar graphs". Discrete & Computational Geometry 42: 570. doi:10.1007/s00454-008-9125-3. 

• Josef Cibulka (2009). "Untangling Polygons and Graphs". Discrete & Computational Geometry 43: 402. doi:10.1007/s00454-009-9150-x. 

• Janos Pach and G. Tardos (2002). "Untangling a polygon". Discrete & Computational Geometry 28: 585–592. doi:10.1007/s00454-002-2889-y. 

• Xavier Goaoc, Jan Kratochvíl, Yoshio Okamoto, Chan-Su Shin, Andreas Spillner and Alexander Wolff (2009). "Untangling a Planar Graph". Discrete & Computational Geometry 42: 542. doi:10.1007/s00454-008-9130-6. 

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
• Planetary — Version using SVG and the d3 JavaScript library