GRAPH Course
Planar graph
A planar graph (Graphe planaire
), is a graph that could be drawn without having two edges crossing each other. We are calling planar representation/Graphe planaire topologique
, the planar representation of a planar graph.
When we are drawing a planar graph, we will have
Face
Do you know the bucket tool in image editors? A face is something colored by the bucked tool in one go. You got at least one unbounded face, which is the one not colored after coloring all of your faces.
A face is a surface of the graph delimited by edges. It can be either a
 bounded face/
face finie
 external, outer or unbounded face/
face infinie
Dual graph
We are calling Dual graph (Graphe dual
), the graph made using the faces as vertices. If we have two faces $F_1$ and $F_2,$ and if $A \in F_1$ was adjacent to $B \in F_2$ then we have $F_1$ is adjacent to $F_2$.
Bounds
Note that you can only use a vertex once inside the bounds (Frontière/contour
) of a face. The bounds are a list of edges you used to delimit a face. The bounds are forming a cycle basis in a planar representation.
Graph minor
You can get the minor of a graph by
 removing an edge
 contracting an edge (the vertex and their edges are merged)
 deleting an edge having a degree of one (isolated, $d(vertex) = 1$)
Check if the graph is planar
Let $m=\#edges=E$, $n=\#vertices=V$ and $f=\#faces$, then a graph is planar if
 Euler's formula: $nm+f=2$ (you can find $f$ with $f=mn+2$)
 if $m < 3n  5$ in a connected graph

Kuratowski's theorem
 The graphs $K_{3,3}$ and $K_5$ are not planar
 A subgraph of these is not planar

Robertson–Seymour theorem
 A graph minor of $K_{3,3}$ and $K_5$ is not planar
Other notes
 if the $\forall{i \in V},\ d(i) \gt 5$, the graph is NOT planar
 if a graph is planar, then $\exists{i \in V},\ d(i) \lt 6$
 According to the English wikipedia, a graph is planar if
 $m \le 3n  6$ (yeah it's 6 not 5)
 $f \le 2n  4$
 if there are no cycles of length 3, $m \le 2n4$
Example 1
Are the following graphs planar?
The first graph is planar because it's $K_5$.
The second one is planar, because I found a planar representation. Notice that we have $n + m = f = 2$ ($n=5$, $m=9$, $f=6$=five+the outer face)
The third graph has a subgraph $K_{3,3}$ so it's not planar.
The fourth graph $m=12 \le 6 * 3  5 \le 13$ so the graph is planar. Simply move the vertices "4" and "5".
All degrees are equals to $6$, so the graph is not planar. We could have used $m < 3n  5$.
As for the sixth graph, it's not planar either. I used Robertson–Seymour theorem and found that the minor of the graph (by only merging vertices) is $K_6$ so if I remove one more vertex, it's $K_5$ and $K_5$ is not a planar graph.
Example 2
Use Robertson–Seymour theorem and demonstrate that the Petersen graph is not planar.
This answer can be found on Wikipedia source. Here is a copy