# Mathematicly Untangeling Untangle.

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)

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.....

## 2 Answers

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.

• The size of a graph is dependent on the amount of edges, so the smallest non-planar graph is actually $K_{3,3}$ – Tim Ratigan Mar 4 '14 at 14:24
• @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. – fgp Mar 4 '14 at 15:09
• @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. – Steven Stadnicki Mar 5 '14 at 22:31

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 :)