How to find the planar embedding of a graph in general?

Question

I need to find the planar embedding of a graph in general if one exists and specifically want to solve the problem for the graph in the figure below. I am acquainted with the graph algorithms but have much less knowledge of the sound mathematical theory underlying graphs. It would be great if someone could throw some light on this.

Answer 1

I can't find any reference for the definition of a face I have always used (it goes into half-edges and half-edge orderings and stuff), but I shall try to explain how you can tell whether the graph has a planar embedding. (I hope it is clear enough!)

Pick a vertex, and travel along some edge. When you get to the next vertex, take the next edge clockwise round the vertex, and repeat, until you are back at your start vertex so that you would repeat the path if you carried on (you might get back to the start but carry on elsewhere!). This has given you the boundary of one face. Pick some other vertex, and do the same, finding another face. This process shall repeat until you have traversed each edge twice, once in either direction. You should not have to traverse an edge more than twice! (or once in the same direction). Once you are done, you know how many faces the graph has (how many of these closed paths there were).

So now you will know how many edges, vertices and faces the graph has, so now you can apply the formula $\xi = V-E+F=2-2g$. If you solve to get $g=0$, then the graph has a planar embedding, and not otherwise.

Answer 2

This graph pictured has order $n=12$ and size $m=30$. Since $m\le 3n-6$, it might have a planar embedding.

However, a graph is planar if and only if it does not contain a either $K_5$ or $K_{3,3}$ as a minor (Wagner's Theorem). So if you can find a sequence of vertex contractions that result in either $K_5$ or $K_{3,3}$, then there is no planar embedding of the graph.

I am not aware of any kind of general algorithm that will build a planar embedding from a given graph.

Answer 3

Note that your graph has $m= 3n-6$ so that if it is planar then all faces must be triangles. Since it is a 5-regular graph then it must be the graph of the icosahedron (a platonic solid):

You can see that your graph is planar by taking, for instance, most of the horizontal edges and moving them outside of the cycle until there are no crossings left.

A generalisation of this method is explained on page 21 of my coursenotes; basically you start with a planar subgraph and repeatedly add in edges (or paths) only when there is only one face which can accomodate it.