Planar and Non-Planar Graphs
Two edges crossing on the page is a fact about how you drew the network, not about the network itself. Some networks can always be redrawn to remove every crossing, and some can never be, and telling the two apart is what this lesson is for.
Lesson 1 established that the position of a vertex carries no information. If you are free to move the vertices anywhere, what does that let you do about a crossing in your diagram?
A graph is planar if it can be drawn in the plane with no two edges crossing, even if the drawing in front of you has crossings. It is non-planar if no drawing avoids them, however cleverly you rearrange it.
$$\text{planar} \iff \text{some drawing has no crossings}$$
Read the definition carefully. Planar is about what is possible, not about what is in front of you. A drawing with crossings proves nothing on its own, because the next drawing might have none.
Know
- that a planar graph is one that can be drawn in the plane so that no two edges cross
- that a non-planar graph is one that can never be drawn without some edges crossing
- that the complete graph on five vertices and the three-utilities graph are the two basic non-planar graphs
Understand
- why a crossing in a drawing is a property of that drawing rather than of the network
- why producing one crossing-free drawing settles planarity but no number of crossing drawings settles non-planarity
- why planarity matters in the design of circuits and interchanges
Can Do
- redraw a graph shown with crossings so that no two edges cross, where this is possible
- recognise the three-utilities problem as a question about planarity
- explain why a point where two edges cross is not a vertex
When two edges cross in a diagram, nothing happens at the crossing point. It is not a vertex. A traveller moving along one edge cannot switch to the other there, any more than a driver on a bridge can turn onto the road passing underneath.
That is worth stating plainly, because a crossing looks like a junction and the eye reads it as one.
Since the positions of vertices carry no information, you are free to move them. Moving a vertex changes the drawing but not the network, and it may remove a crossing.
So "this drawing has a crossing" is a statement about the page, not about the mathematics. The interesting question is whether every possible drawing has one.
A graph is planar if it is possible to draw it in the plane with no two edges crossing. A graph is non-planar if this is impossible.
Notice the asymmetry in how the two are established.
To show a graph is planar, produce a single crossing-free drawing. That one drawing settles it completely, and nobody can argue with it.
To show a graph is non-planar you would have to rule out every drawing, and there are infinitely many. Failing to find a good drawing is not evidence of anything beyond your own patience. Non-planarity needs an argument, and Lesson 5 supplies one.
A crossing-free drawing of a planar graph is called a planar drawing of it. The graph is planar; a particular drawing is or is not planar.
Three moves solve most cases, and all three are legitimate because they change only the picture.
Move a vertex. Drag it to a new position and redraw its edges. The square-with-diagonals in the diagram becomes crossing-free when one vertex is moved into the middle of the triangle formed by the other three.
Route an edge the long way round. An edge does not have to be a straight line. Curving it around the outside of the whole diagram often clears a crossing that a straight line could not avoid.
Turn the diagram inside out. Any face of a planar drawing can be made the outside one by redrawing, which is sometimes the move that unlocks a stubborn diagram.
Work on one crossing at a time and redraw completely rather than patching. A tidy redraw from scratch is usually quicker than repairing a tangle, and it is easier to check.
Some graphs genuinely resist every attempt, and two of them are famous.
The first is the complete graph on five vertices: five dots with every pair joined, giving $10$ edges. Try it and you will always be left with one edge that has nowhere to go.
The second is the three-utilities graph: three houses and three utilities, with every house joined to every utility, giving $6$ vertices and $9$ edges. The puzzle asks for gas, water and electricity to reach all three houses without any pipe crossing another, and it has circulated as a brain-teaser for more than a century.
Both are impossible, and the puzzle has no solution. That is not a failure of ingenuity; it is a theorem, and Lesson 5 proves the first case using Euler's formula.
These two are more important than they look. A famous result states that a graph is non-planar exactly when it contains one of these two hidden inside it, so between them they account for every non-planar graph there is.
Planarity is not a curiosity. It is a constraint that costs money.
On a printed circuit board, conducting tracks lie on the surface and two tracks that cross would short together. If the circuit's network is planar, one layer suffices. If it is not, the board needs a second layer and small holes called vias to pass between them, which raises the price of every unit made.
On a road network, a crossing needs a bridge, a tunnel or a set of traffic lights, and each is expensive. Designers work hard to keep the network of a junction planar for exactly this reason.
In chip design the same question appears at microscopic scale and with millions of edges, which is why efficient tests for planarity are a genuine part of the industry.
In each case the mathematical question and the engineering question are the same question: can this be laid out flat, or must we go up a level?
Watch Me Solve It · 3 examples
-
1List the edges$AB, \ AC, \ AD, \ BC, \ BD, \ CD$Six edges, since every pair of the four vertices is joined. Any redrawing must reproduce exactly this list.
-
2Choose a vertex to moveDraw $A$, $B$ and $C$ as a triangle, using the edges $AB$, $BC$ and $CA$. That uses three of the six edges with no crossing.
-
3Place the fourth vertex insidePut $D$ in the middle of the triangle and join it to $A$, $B$ and $C$. Those three edges radiate outwards to the corners and cannot cross each other or the triangle.
-
4Check and concludeAll six edges are drawn and no two cross, so this is a planar drawing. The graph is therefore planar, and the crossing in the square version was a feature of that drawing alone.
-
1Identify which edges are the problemWith the vertices around a circle, the edges joining neighbours run around the rim without trouble: $PQ$, $QR$, $RS$, $ST$ and $TP$. The remaining edges $PR$ and $QS$ are chords and cross each other.
-
2Move one chord to the outsideAn edge may be drawn as any curve. Route $PR$ around the outside of the circle rather than across it, passing outside $Q$.
-
3Check for new crossingsOutside the circle there is nothing else drawn, so the re-routed $PR$ meets no other edge. The chord $QS$ is now alone inside the circle and crosses nothing.
-
4ConcludeEvery edge is drawn and no two cross, so the graph is planar. Note that only the drawing changed; the edge list is the same seven edges throughout.
-
1Set up the modelVertices are the three houses and the three utilities, giving $6$ vertices. An edge joins a house to a utility when that house must be connected to it.
-
2Count the edges$3 \times 3 = 9$Each of the three houses needs all three utilities, so there are nine connections. No house is joined to another house and no utility to another utility.
-
3Restate the puzzle"No pipe crosses another" is exactly the requirement that the graph be drawn with no two edges crossing. So the puzzle asks whether this graph is planar.
-
4State the answerThis graph is non-planar, so the puzzle has no solution. Every attempt leaves one connection unmade, and no amount of ingenuity will help, because the obstruction is a theorem rather than a lack of cleverness.
Brain Trainer · 5 problems
Five items on planarity. Remember that the definition asks what is possible, not what is drawn.
-
1 A graph is drawn with three crossings. Is it non-planar?
The definition asks whether some drawing avoids all crossings.Not necessarily; try redrawing -
2 What must you produce to prove a graph is planar?
One example is enough for an existence claim.A single crossing-free drawing -
3 How many edges does the complete graph on five vertices have?
Every pair of the five vertices is joined, and there are $\tfrac{5 \times 4}{2}$ pairs.$10$ -
4 At a point where two edges cross, can a traveller change from one edge to the other?
A crossing is not a vertex.No -
5 Why does planarity matter for a printed circuit board?
Two conducting tracks that touch would short together.A planar circuit fits on one layer
Multiple Choice · 5 questions
A graph is planar if:
In a drawing of a network, a point where two edges cross:
A student produces one drawing of a graph in which no two edges cross. This shows the graph is:
The three-utilities puzzle asks for three houses to be joined to three services with no crossings. In graph terms the puzzle asks whether a certain graph is planar. That graph has:
A circuit's network is found to be non-planar. The practical consequence is that:
Short Answer · 3 questions
Planar means redrawable
A graph is planar if some drawing has no crossings. The drawing in front of you having crossings says nothing about the graph.
A crossing is not a vertex
Nothing happens where two edges cross, and no traveller can change edges there. It is an artefact of flat paper.
One drawing proves planar; nothing short of an argument proves non-planar
Existence claims yield to a single example. Ruling out every possible drawing needs a theorem, which Euler's formula supplies.
Two graphs account for all non-planarity
The complete graph on five vertices and the three-utilities graph. A graph is non-planar exactly when one of them is hidden inside it.
Your Badges
0 of 6Mark lesson as complete
Tick when you've finished Learn, Practice and the Stretch. Earns +90 XP and +25 coins.