I need to prove that if graph $G$ is planar, then a graph created from it by joining two vertices $v,u$ on edge $e$ and connecting to a newly created vertex all others that were connected to either $v,u$ (and creating $G'e$ in the process) is planar too. Here's and example: 
How in the world should I prove that? It's obvious that a graph created this way satisfies the Euler formula for planar graphs, but is it indeed planar?
Hint: use Kuratowski's theorem to prove that you can't induce some $K_5$ or $K_{3,3}$ in $G/e$.