Proving that a graph is a planar graph

Question

I looked at some problems where I had to prove that a graph is a planar graph. What methods are there to do this?

For example:

Is there a 4-regular graph with 16 vertexes which is a planar graph?

Answer 1

There are two general ways:

• show an embedding into $\mathbb{R}^2$, hence graph is planar,
• show it contains $K_5$ or $K_{3,3}$ as a minor, thus graph is not planar.

In your case you could use the following feature to construct a graph with an embedding (this only shows that there exists a 4-regular planar graph):

Also, it's not hard to construct a non-planar 4-regular graph, e.g.

The red part is $K_{3,3}$ while blue edges make the graph connected (otherwise the graph is 3-regular).

I hope this helps ;-)