Planarity

From Johnwiki

Planarity is a web game that I made in 2005 based on an idea of Mary Radcliffe's. The official website is planarity.net.

Contents 1 Generating Planar Graphs 1.1 Notice 1.2 Algorithm 1.3 Psuedocode 1.4 Pair Index 2 Other Implementations

[edit] Generating Planar Graphs

[edit] Notice

Please note that this algorithm is offered "as is" and with no warranty or guarantee. Although this algorithm is not patented and algorithms cannot be copyrighted, I consider it a significant work of mine. That said, if you wish to use or modify the algorithm below, please consider citing me, John Tantalo, as a courtesy.

[edit] 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.

[edit] Psuedocode

Input: a list L of n 2-dimensional lines

Let G be a graph.

Add n(n-1)/2-1 vertices to G.

For each line p in L:

Let M = L without p.

Order M by the order that the lines in M intersect p.

For each pair M_i and M_i+1:

Let u = PairIndex(p, M_i, n), v = PairIndex(p, M_i+1, n).

Add an edge (u, v) to G.

Return G.

We assume L and M index from 0.

[edit] 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 0 and (n(n-1)/2)-1, the range of vertices.

Definition

If 0 <= p < q < n, then PairIndex(p, q) = (p(2n-p-1)/2)+q-p-1, where n is the number of lines.

Claim

PairIndex is a bijection (i.e., one-to-one and onto) between {(p, q) | 0 <= p < q < n} and {0 ... (n(n-1)/2)-1} for any fixed n.

Proof

Coming soon. It's true, I swear.

[edit] Other Implementations

• Multi-Touch Interaction System by Jeff Han (video)
• gPlanarity by Monty, written in GTK+.
• TangleBee by SmartMelon Games, for Windows.
• Tangle by MC Hot Software, for Mac OS X.
• Planar Game by Eric Abouaf, written in Javascript using the WireIt library.
• Untangle by Chris Benjaminsen, written in Flash.
• UntangleManiak by PuzzleManiak (Alexandre Minard), for the iPhone