Planar Graphs

When drawing graphs, we usually try to make them look “nice”.
- Of course, there's no obvious definition of that.
- But one thing we probably do want if possible: no edges crossing.
- For example, the drawing on the right is probably “better”
Sometimes, it's really important to be able to draw a graph without crossing edges.

From Wikipedia Testpad.JPG.
- From the text: connecting utilities (electricity, water, natural gas) to houses. If we can keep from crossing those lines, it will be safer and easier to install.
- Connecting components on a circuit board: the connections on a circuit board cannot cross. If we can connect them without resorting to another layer of traces, it will be cheaper to produce.
- Subway system: if subway lines need to cross, we've got some serious engineering to do.
A graph that can be drawn on a plane without edges crossing is called planar.
For example, we drew \(Q_3\) in a non-planar way originally, but it is actually planar:
- Like being bipartite or isomorphic, we can't just draw the graph one way and decide it's not planar.
- There might be another way to draw it so it is planar.

Euler's Formula

When we draw a planar graph, it divides the plane up into regions.
- For example, this graph divides the plane into four regions: three inside and the exterior.
- While we're counting, on this graph \(|V|=6\) and \(|E|=8\).
It's maybe not obvious that the number of regions is the same for any planar representation of this graph.
- …or any representation of a particular planar graph.
Theorem: [Euler's Formula] For a connected planar simple graph \(G=(V,E)\) with \(e=|E|\) and \(v=|V|\), if we let \(r\) be the number of regions that are created when drawing a planar representation of the graph, then \(r=e-v+2\).

Proof idea: We proceed by induction on the number of edges. For \(e=1\), we can only have this graph, which has \(v=2\) and \(r=1\), so the theorem holds.

If we assume the conclusion for \(e-1\) edges, and add an edge to get our planar graph, there are only two possibilities to consider.
Case 1: we add a pendant vertex and edge. In this case \(e\) and \(v\) both increase by one and the equality still holds.

Case 2: we add an edge across two existing vertices (that doesn't cross any other edges, of course). Here, \(r\) and \(e\) both increase by one, preserving the equality.

So we can build any planar graph with \(e\) edges and it will always have \(r=e-v+2\).
For example:
- \(Q_3\) has \(r=6\), \(e=12\), and \(v=8\).
- \(C_n\) has \(r=2\), \(e=n\), and \(v=n\).

Testing for Planarity

We know a way to decide that a graph is planar: draw it without edges crossing.
- … but that's all we know so far.
- It would be nice to have a way to decide for sure whether or not a graph is planar, without worrying that we haven't been clever enough in our drawing.
Here are two graphs I promise aren't planar: \(K_{3,3}\) and \(K_5\).
- We don't have any theorems for that (yet), but any way you try to draw them, you'll eventually be unable to draw some of the edges without crossing.
- In some way, these are the “smallest” non-planar graphs.
- We'll see what “smallest” means soon.
Theorem: For a simple connected planar graph with \(v\ge 3\) vertices and \(e\) edges, \(e\le 3v-6\).

Proof: Let \(r\) be the number of regions in a planar representation of the graph, and for a region \(R\), let \(\operatorname{deg}(R)\) be the number of edges that are adjacent to the region, so each edge is adjacent to two regions.
We know that \(\operatorname{deg}(R)\ge 3\) for each region since the graph doesn't have multiple edges (for interior regions) and has at least three vertices (for the exterior region). Since each edge is adjacent to two regions, \[2e=\sum \operatorname{deg}(R) \ge 3r\,.\]
We can use this with Euler's formula (\(r=e-v+2\)) to get \[\begin{align*} 3r &\le 2e \\ 3(e-v+2) &\le 2e \\ e &\le 3v-6\,.\quad ∎ \\ \end{align*}\]
This theorem isn't if-and-only-if, so be careful.
- It does show that \(K_5\) is non-planar: \(v=5\), \(e=10\).
- But for \(K_{3,3}\), we have \(v=6\) and \(e=9\). It satisfies the inequality, but is non-planar.
Corallary: A simple connected planar graph with \(v\ge 3\) has a vertex of degree five or less.

Proof: Suppose every vertex has degree 6 or more. Then the total number of edges is \(2e\ge 6v\). But, because the graph is planar, \[\sum \operatorname{deg}(v) = 2e\le 6v-12\,. \] We have a contradiction.∎
Theorem: For a simple connected planar graph with \(v\ge 3\) vertices and \(e\) edges, and no circuits of length three, \(e\le 2v-4\).

Proof idea: Since we have no loops of length three, we can repeat the above proof with \(\operatorname{deg}(R)\ge 4\).
This theorem should convince you that \(K_{3,3}\) is non-planar: \(v=6\) and \(e=9\).
- There are still graphs that obey this inequality, but are non-planar.
- Here's one with \(v=15\) and \(e=18\):
- … and I know it's not planar because of the next theorem.

Kuratowski's Theorem

It turns out that \(K_{3,3}\) and \(K_5\) are the “smallest” non-planar graphs in that every non-planar graph contains them.
- … but not simply as subgraphs: the above example doesn't have either as a subgraph.
We will take a more permissive version of “contains” here: contains a graph homeomorphic to.
- One graph is homeomorphic to another if you can turn one into another by adding or removing degree-two vertices:
Theorem: [Kuratowski's Theorem] A graph is non-planar if and only if it contains a subgraph homeomorphic to \(K_{3,3}\) or \(K_5\).
A graph is non-planar iff we can turn it into \(K_{3,3}\) or \(K_5\) by:
1. Removing edges and vertices. (Making a subgraph.)
2. Collapsing degree-two vertices into a single edge.
3. Applying an isomorphism to turn it into \(K_{3,3}\) or \(K_5\).
This animation explains it better than I ever could: the starting graph here can be turned into \(K_{3,3}\) by these operations.

From Wikipedia Kuratowski.gif.