Newsgroups: rec.puzzles
From: Dan Hoey <haoyuep@aol.com>
Date: Sun, 10 Aug 2008 21:39:05 -0400
Subject: Re: Planarity

Steven Jones wrote:
> The multi-agent software Netlogo now includes a puzzle game
> called Planarity as one of its example models.  The puzzle
> involves a graph with seemingly randomly connected nodes.  The
> object is to move the nodes so that none of the links overlap.
> Is there a general solution for this game?  I've made it
> to level 6.

Fáry's theorem ( http://en.wikipedia.org/wiki/F%C3%A1ry%27s_theorem )
states that any planar graph has a straight-line embedding.  There
is software available for constructing such an embedding; google for
"planar graph" "straight line embedding" .

Presumably Netlogo generates a planar graph and randomizes the
placement its vertices, or even searches heuristically for a vertex
placement maximizing the number of crossings.

Dan Hoey
haoyuep at aol.com