Wagner's theorem states that a graph is planar if and only if it does not contain a minor that is isomorphic to $K_5$ or $K_{3,3}$. An undirected graph H is called a minor of the graph $G$ if $H$ can be formed from $G$ by deleting edges and vertices and by contracting edges.
On the other hand, here and here it's said that the algorithm of planarity testing (non-polynomial, of course) could look like:
1) Choose an edge of G
2) Shrink it
3) If $6$ vertices are remaining - check for $K_{3,3}$, if $5$ - check for $K_{5}$
4) Repeat for all combinations
Question: Is the aforementioned algorithm valid? It seems that the algorithm performs only the contractions. However, minors could also be formed by deleting edges and vertices.
Thank you for your help!
The algorithm works as long as you start with a connected graph.
It may be easier to see this from Kuratowski's Theorem which characterizes non-planar graphs as graphs that have a subdivision of $K_5$ or $K_{3,3}$ as a subgraph.
Say your graph has a subdivision of $K_5$ with vertices $v_1,\dots,v_5$ being the five main vertices of the subdivision. Contract all the edges of $G$ except any edge $v_iv_j$ for $1\leq i< j\leq 5$. This will give you a $K_5$. The case where your graph contains a $K_{3,3}$ follows identically.