Graph Theory proving planarity

Here's an illustration of a subgraph of $G$ which is a subdivision of $K_5$, so Kuratowski's Theorem implies $G$ is non-planar:

Here's a planar drawing of $H$, demonstrating that it's planar:

If it contained a subgraph which is a subdivision of $K_5$ or $K_{3,3}$, this planar drawing would not be possible.

Both of these graphs have spanning cycles. There is an algorithmic way to check if a graph with a spanning cycle is planar using the concept of a "conflict graph".

Pick a spanning cycle, and draw the graph with that spanning cycle as a circle, and all the edges off the spanning cycle as chords of that circle. For the first graph, I chose the cycle a, b, f, d, e, g, c. My graph drawing software (Sage) is awkward with vertex labels, and so here I've named them respectively 1, 2, 3, and so on.

The conflict graph is a new graph in which the vertices are the chords of this drawing of your graph. Two chords are considered to "conflict", and are thus adjacent in the conflict graph, if and only if they cross in the above drawing. The idea is this. Let G be your graph and C the spanning cycle. Any planar embedding of G must represent C as some sort of a closed curve - not necessarily a circle, but some closed curve which will divide the plane into an inside and an outside. If two chords conflict, then they necessarily have to be drawn on different sies of this curve (one outside and one inside) in order not to cross.

The conflict graph here looks like this:

The theorem is: a graph with a spanning cycle is planar if and only if its conflict graph is bipartite. This is obvious given what we said above: we need a 2-coloring for the conflict graph using the colors "inside" and "outside". If the conflict graph is non-bipartite, two chords will necessarily have to be drawn on the same side of the cycle. In this case, the conflict graph is obviously non-bipartite since it has an obvious odd cycle.

You can read more about conflict graphs in Douglas West's book, Introduction to Graph Theory.

Graph $G$ is not planar. The subgraph you get by deleting the edges $ab,$ $ad,$ $bd,$ $cg,$ $eg$ is homeomorphic to $K_{3,3};$ the vertices $a,b,d$ are connected to the vertices $e,f,g$ by the internally disjoint paths $ace,$ $af,$ $ag,$ $be,$ $bf,$ $bg,$ $de,$ $df,$ $dg.$

Graph $H$ is planar. Plot $a$ at $(0,0),$ $b$ at $(2,0),$ $c$ at $(1,1),$ $d$ at $(1,3),$ $e$ at $(1,4),$ $f$ at $(2,3),$ $g$ at $(1,2),$ and draw all the edges as straight line segments.