What is simplest polynomial algorithm for PLANARITY? There are several algorithms that decide in polynomial time whether a graph can be drawn in the plane or not, even many with a linear running time. However, I could not find a very simple algorithm that one could easily and fast explain in class and would show that PLANARITY is in P. Do you know any?
If necessary, you can use Kuratowski's or Fary's theorem but no deep stuff, like the graph minor theorem.
Also note that I do not care about the running time, I just want something polynomial.
Below are the so far 3 best algorithms, showing a simplicity/no-deep-theory-needed trade-off.

Algorithm 1: Using that we can check whether a graph contains a $K_5$ or a $K_{3,3}$ as a minor in polynomial time, we get a very simple algorithm using deep theory. (Note that this theory already uses graph embeddings, as pointed by Saeed, so this is not a real algorithmic approach, just something simple to tell students who already knew/accepted the graph minor theorem.)
Algorithm 2 [based on someone's answer]: It is easy to see that it is enough to deal with 3-connected graphs. For these, find a face and then apply Tutte's spring theorem.
Algorithm 3 [recommended by Juho]: Demoucron, Malgrange and Pertuiset (DMP) algorithm. Draw a cycle, components of remaining graph are called fragments, we embed them in a suitable way (meanwhile creating new fragments). This approach uses no other theorems.
I am going to describe an algorithm. I am not sure it qualifies as "easy" and some of the proofs are not so easy. 

First we break the graph into 3-connected components, as mentioned by Chandra Chekuri.


Break the graph into connected components.
Break each connected component into 2-connected components. This can be done in polynomial time checking for each vertex $v$ of each 2-connected component $G_i$ whether $G_i-v$ is connected. 
Break each 2-connected component into 3-connected components. This can be done in polynomial time checking for two distinct vertices $v,u$ of each 2-connected component $G_i$ whether $G_i-\{ v,u \}$ is connected. 


We have reduced the problem to checking whether a 3-connected component of the graph is planar. Let $G$ denote a 3-connected component.


Take any cycle $C$ of $G$. 
Pin the vertices of $C$ as vertices of a convex polygon. Put each of the other vertices in the barycenter of its neighbors. This leads to a system of linear equations telling the coordinates of each vertex. Let $D$ be the resulting drawing; it may have crossings. 
If $D$ has no crossings, we are finished.
Take the vertices $U$ in any connected component of $G-V(C)$. The restriction of $D$ to the induced subgraph $G[U\cup V(C)]$ should be planar. Otherwise, $G$ is not planar. Take any face $F$ in the drawing $D$ restricted to the induced subgraph $G[U\cup V(C)]$, and let $C'$ be the cycle defining $F$. If $G$ is to be planar, then $C'$ must be a facial cycle. (When $C$ is a Hamiltonian cycle, then $C'$ should be constructed using an edge.)
Repeat step 2 with C' instead of C. If the resulting drawing is planar, then $G$ is planar. Else $G$ is not planar.


Remarks: 


Arguing that Tutte's spring embedding gives a planar embedding is not straightforward. I liked the presentation in the book of Edelsbrunner and Harer, Computational Topology, but it is only for triangulations. Colin de Verdiere discusses the spring embedding in http://www.di.ens.fr/~colin/cours/algo-graphs-surfaces.pdf , section 1.4. A general reference is Linial, Lovász, Wigderson: Rubber bands, convex embeddings and graph connectivity. Combinatorica 8(1): 91-102 (1988).
Solving a linear system of equations in a polyomial number of arithmetic operations is easy via Gaussian elimination. Solving it using a polyonomial number of bits is not that easy.