Matpic
mathematics, in pictures
Series

Planarity — the series

5 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. Two graphs that will not lie flat, and one that will. K4, K5 and K3,3 in the best straight-line drawings a search could find. K4 has no crossings; the other two have one each, and Euler's formula shows that none can have none.

    Two graphs that will not lie flat

    Five points, every pair joined: no matter how the points are placed or how the lines are drawn, two of the lines cross. The proof is not about drawing at all — it counts edges against faces and finds one edge too many.

    part 1 · discrete
  2. The Petersen graph, which a five-edge count rules off the plane. The Petersen graph drawn as an outer pentagon, an inner pentagram and five spokes: ten points, fifteen edges, girth five, and more edges than the 13.33 a flat drawing with five-edge faces allows.

    Five spokes squeezed into K5

    The Petersen graph has no point with four neighbours, so no stretched copy of K5 can sit inside it. Contract its five spokes and K5 appears anyway. Kuratowski's theorem forbids stretched copies and Wagner's forbids squeezed ones, the two notions disagree on this graph — and they still name exactly the same planar graphs.

    part 2 · discrete
  3. Breadth-first levels in a planar triangulation. A Delaunay triangulation of 160 random points with each point coloured by whether it is inside, on or outside the level 4 steps from the centre; that level of 23 points separates 31 from 106.

    The few points that cut a flat graph

    Any graph that can be drawn without crossings, however large, falls into pieces of at most two thirds once a few points are removed — about the square root of its size, never more than 2.83 times it. A grid shows the square root cannot be beaten, a ring of breadth-first neighbours comes close, and a cycle through a shallow tree finishes the job.

    part 3 · discrete
  4. The complete graph on 7 points, drawn straight with 9 crossings. A straight-line drawing of the complete graph on 7 vertices with 9 crossings, the minimum for straight drawings; each crossing comes from four vertices in convex position.

    The crossings a graph cannot avoid

    Five points all joined need one crossing, six need three, seven need nine. Euler's formula gives a lower bound that grows like the square of the number of points and is badly wrong; a sampling trick turns the same formula into a bound that grows like the fourth power and is right to within a constant. And for drawings with straight edges the count turns out to be something else entirely: the number of quadrilaterals the points make.

    part 4 · discrete
  5. The cube drawn by putting every point at the average of its neighbours. Tutte's barycentric drawing of the cube: outer face of 4 sides, 0 crossings.

    Every point at the average of its neighbours

    A planar graph can be drawn without crossings, but finding such a drawing looks like a search. Tutte found in 1963 that it is not: pin one face to a convex polygon, put every other point at the average of its neighbours, and the drawing that results has straight edges, convex faces and no crossings at all — provided no two points can cut the graph apart. It is the position a network of equal springs settles into, and it is also where a random walk expects to leave.

    part 5 · discrete

All series