Planarity - a game with planar graphs

http://www.planarity.net/

by infinity • 17 years ago

33 14 17 years ago

This is pretty choice - reminds me of untangling a circuit layout... Never really looked into it that much, but I'd imagine there must be a mathematical technique that can be applied. My first instinct has always been to put the point with the most connections in the centre, then map out from that.

eru3• 17 years ago

Good luck. The problem may be NP complete in general.

shrughes• 17 years ago

Well, for the cases on planarity.net, it seems O(n) to me. Or maybe something like O(n log n)

boblol123• 17 years ago

Take the vertex whose vertices cross the biggest number of other vertices and move it. Repeat until nothing crosses. I remember this problem in maths ages ago, there is a way to know if you can't untangle something- look up the water gas electricity problem

gjm113• 17 years ago

A graph is nonplanar if and only if it has a subgraph that looks like either (1) five vertices all connected to one another or (2) two sets of three vertices, with every vertex in one set connected to every vertex in the other.

"Looks like" means: can be turned into by repeatedly replacing -o- (a vertex with two edges coming out of it) with -- (a single edge between the vertex's two old neighbours).

See http://en.wikipedia.org/wiki/Planar_graph for details.

barrettcolin• 17 years ago

Spooky: there is an almost identical iPhone game called 'The Plateau'. Screens here: http://www.tuaw.com/photos/the-plateau/1270610/

smanek• 17 years ago

I remember playing playing Planarity well before the iPhone came out, so 'The Plateau' is just a copy.

In fact, the "Way Back Machine" shows Planarity, basically unchanged, in 2005: http://web.archive.org/web/20050731231914/http://www.planari...

derwiki• 17 years ago

I think this game won John "One of the Most Interesting People In Cleveland" when he wrote this sophomore year at CWRU. I'm happy to see that his project is still being enjoyed!

gord• 17 years ago

Highly addictive... Got to 1500 odd, had a sneak peak at level 30 then gracefully bowed out.

Used a combination of heuristics - move a vertex to the centroid of its neighbors, and move randomly to reduce edge intersections.

eyes burning.

madair• 17 years ago

It would be interesting to couple this game with user profiles that include questions related to mysteries and observations in cognitive science. Thinks like left/right handed, formal education, would be interesting too.

Planarity - a game with planar graphs

Related Stories