Untangle puzzles explained: what makes a graph planar?

Learn why an untangle puzzle can have crossing lines and still be planar. Move a point, compare two drawings and see what Euler's formula can tell you.

Two drawings of the same four-point graph, with a crossing on the left and a triangle around its fourth point on the right

An untangle puzzle asks you to move dots until their connecting lines stop crossing. The mathematical idea behind it is a planar graph: a network that can be drawn on a flat surface without edges crossing, except where they meet at a shared endpoint. The important words are can be drawn. A drawing full of crossings does not, by itself, tell you that the graph is nonplanar.

In Pyxis, I call the dots knots and the lines strands. Moving a knot changes the drawing, while its connections stay attached. That difference between a network and its current picture explains much of what an untangle puzzle is asking you to see.

A graph and a drawing are different things

Imagine four points called A, B, C and D, with every pair joined. There are six connections: AB, AC, AD, BC, BD and CD. Mathematicians call this complete graph K4.

Put the four points at the corners of a square and the two diagonals cross. Put three at the corners of a triangle and the fourth inside it, and all six connections fit without a crossing. The graph has not changed. The position of one point has.

The diagram below uses this four-point example to show the distinction. It is a mathematical illustration, separate from the game’s levels.

Same six connections, different drawing

Move D sideways. A, B and C stay still, and every point stays connected to the other three.

ABCD

1 pair of edges crosses away from its endpoints.

Connections: AB, AC, AD, BC, BD and CD. Shared endpoints are allowed.

Moving the point can create or remove a crossing without adding or deleting an edge. In graph theory, the graph describes the connections. The drawing describes where the points and lines sit.

What counts as a crossing?

Two lines meeting at the point they both connect to are allowed. Otherwise, a graph could not have a junction with several connections. The trouble is where two edges meet away from their shared endpoint, or where an edge passes through a point it does not connect to.

In an ordinary planar drawing, edges may curve. In a straight-line untangle puzzle, each connection is drawn as one straight segment. You change its direction by moving an endpoint.

That gives a useful way to inspect a crowded picture. Pick one point and follow each of its attached lines. Look at the connections themselves before trying to make the whole drawing look tidy. A symmetrical picture is not a requirement for planarity.

Euler’s formula gives a useful check

For a connected graph drawn without crossings, let V be the number of vertices, E the number of edges, and F the number of faces. A face is a region of the drawing, including the unbounded region outside it. Euler’s formula says:

V−E+F=2V - E + F = 2

For the triangle-and-centre drawing of K4, there are four vertices, six edges and four faces. Three faces sit inside the triangle and one lies outside. The arithmetic is 4 minus 6 plus 4, which is 2.

Mary Radcliffe’s graph-theory notes at Carnegie Mellon use Euler’s formula to explain why some graphs cannot be planar. One related bound is useful here: a simple planar graph with at least three vertices has at most 3V minus 6 edges. Simple means that a point has no edge to itself and no pair of points has more than one edge between them.

Five points with every pair joined make K5, which has ten edges. The planar bound would allow at most nine. So changing the positions cannot produce a crossing-free drawing of K5. The connections themselves prevent it.

Passing the edge-count check does not prove that a graph is planar. The other classic counterexample, K3,3, has six vertices and nine edges, which is below that general bound, but it is still nonplanar. The same notes explain that case too.

Why a generated untangle puzzle needs more than random lines

If you connect arbitrary pairs of dots, you can make a graph that has no planar drawing. No amount of patient dragging can fix its connections. A puzzle maker needs a reason to know that a clear layout exists.

Pyxis starts with a clear layout and then changes the knot positions. The game keeps the original connections and a valid clear layout. That supplies a known destination instead of relying on the hope that a random graph will untangle. The details are in how every Pyxis web is made.

Planarity alone does not settle every rule a game can add. An anchored point or a point restricted to a track limits which drawings the player can reach. Pyxis places those constraints so its stored clear layout remains available. It also asks for space between knots and between a knot and an unrelated strand, so a mathematically thin drawing is not automatically a clear game board.

Finding a clear drawing and finding the shortest route differ

A graph can have many clear drawings. Even if you know one exists, deciding which points to move can still be a difficult problem. Research by Goaoc and colleagues shows that minimising the number of vertices moved to untangle a straight-line drawing is NP-hard in the general case. Untangling a Planar Graph

That result concerns a precisely defined mathematical problem. It does not measure the difficulty of a particular Pyxis level, and it does not mean that every small untangle puzzle is hard. It explains why the questions “can this be cleared?” and “how few points must move?” deserve separate attention.

For playing, I would start by understanding the connections and clearing the web. The Pyxis rules guide explains its knots, tracks and hints. If you want to try that idea with constellations and changing constraints, see Pyxis on Google Play.

On this page