Planarity is a web game created by John Tantalo in 2005 based on an idea by Mary Radcliffe. The official website is Planarity.net.
This document describes some of the methods used to create Planarity and
Please note that this algorithm is offered "as is" and with no warranty or guarantee.
This algorithm is not patented. I know of no other prior art or patent for this algorithm. Given that, it was first published 3 April 2007 and is now in the public domain.
The specific pseudocode and illustrations below are copyrighted by John Tantalo. The proof is copyrighted by Mary Radcliffe.
I consider the algorithm a significant invention of mine. That said, if you wish to implement, adapt, or modify the algorithm below, please consider citing me, John Tantalo, the author, as a courtesy.
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}
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.
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.
If 1 <= p < q <= n, then PairIndex(p, q) = (p-1)(2n-p)/2+q-p
Many thanks to Manfred Kroehnert and Craig Bailey for improving this definition.
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.
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 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.