9
$\begingroup$

I have a new addiction, I play Untangle to often, and i am wondering what is the mathematics behind it.

some free games: (but be warned highly addictive)

Javascript: http://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/untangle.html

Android: https://play.google.com/store/apps/details?id=softkos.untanglemeextreme&hl=en

the rules are simple:

You are given a number of points, some of which have lines drawn between them. You can move the points about arbitrarily; your aim is to position the points so that no line crosses another.

in some versions the difficulty is enriched by making 1 to 3 points unmovable.

This simple puzzle gives rise to all kinds of topological questions:

  • is there an algorhitms to solve them?

Some of the games in the android download I was unable to solve, and that makes me wonder, probably there are unsolvable untangle puzzles (so that in any situation some lines will cross)

  • how can you recognize them?
  • what are the minimal cases of unsolvable puzzles?
  • are there fundamentaly different cases of unsolvable puzzles?

Are there any mathematical reports written about these puzzles?

see now back trying to solve one.....

$\endgroup$
5
$\begingroup$

There are unsolvable puzzles. Untangle gives you a graph, i.e. a set of vertices (points) with edges (lines) between some of them. You are asked to find an embedding of the graph into the two-dimensional plane such that no two edges cross each other. A graph where that is possible is called a planar graph.

Not all graphs are planar - the smallest non-planar graph is the graph containing 5 vertices, and edges between all pairs of vertices. I.e., you start out with a pentagram, and then draw lines between all pairs of corners.

There are various ways to decide whether a graph is planar - check out http://en.wikipedia.org/wiki/Planar_graph and http://en.wikipedia.org/wiki/Planarity_testing

If you read those articles carefully, you'll notice that it doesn't really say that the edges must be lines - it allows edges to be any kind of curve. That, however, doesn't really make a difference. If you find some embedding of a graph into the two-dimensional plane where the edges - if represented as arbitrary curves - don't intersect one another, you can always move the points around such that these curves become straight lines.

$\endgroup$
  • $\begingroup$ The size of a graph is dependent on the amount of edges, so the smallest non-planar graph is actually $K_{3,3}$ $\endgroup$ – Tim Ratigan Mar 4 '14 at 14:24
  • $\begingroup$ @TimRatigan I went with $K_5$ simply because it was easier to explain what it looks like. But you're right of course that $K_{3,3}$ has fewer edges. $\endgroup$ – fgp Mar 4 '14 at 15:09
  • $\begingroup$ @TimRatigan That depends a lot on your specific notion of size; for algorithm complexity the canonical notion is arguably $|V|+|E|$, but mathematically most folks seem to enumerate graphs by vertex count first, and only then tally edges and such within a given vertex count. $\endgroup$ – Steven Stadnicki Mar 5 '14 at 22:31
0
$\begingroup$

The theory of force directed drawing algorithms(further theory of Tutte's barycenter method ) is the way to solve it if is planar...if is not you drop in the previous answer.

BtW cool game :)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.