Given a planar graph, and an arbitrary prescription for its vertex positions in in the plane. Can you always draw the edges of the graph without crossings (not straight segments, of course) for any given vertex positions?
I guess it is a bit like asking whether there is always a bijective transformation between embeddings of the same graph, because this can be posed as a deformation problem from the canonical straight-edge embedding.
Lemma: Given two points $z_0$ and $z_1$ in the complex plane $\mathbb{C}$, for every finite set of points $S\subset\mathbb{C}$ which does not include either $z_0$ or $z_1$, there exists a continuous bijection $M:\mathbb{C}\rightarrow\mathbb{C}$ s.t. $M(z_0)=z_1$, $M(z_1)=z_0$ and $M(s)=s$ for all $s\in S$.
Proof: The lemma is obviously true if $z_0=z_1$, so we can assume they are distinct. First consider the easy case where $z_0 = 1$, $z_1 = -1$ and $S=\emptyset$. Let $B_\epsilon(x)$ be a one-dimensional bump function with support $[1-\epsilon,1+\epsilon]$, where $\epsilon\in(0,1)$ such that $B_\epsilon(1)=1$. Then the function $M_\epsilon(z)=\lvert z\rvert e^{i(\arg(z)+\pi B_\epsilon(\lvert z\rvert))}$ is a continuous bijection of the required type which leaves all points outside of the annular ring centered at the origin with radii in the range $[1-\epsilon,1+\epsilon]$ unchanged. (A non-rigorous description of this transformation is that starting at radius $1-\epsilon$ each circle centered at the origin is rotated gradually more and more until the circle of radius 1 is rotated by 180 degrees, which switches between 1 and -1, and then the circles of radius greater than one are gradually rotated less and less until we get to radius $1+\epsilon$.)
For the more general case, there exists an invertible affine transformation of the plane $A$ s.t. $A(z_0)=1$ and $A(z_1)=-1$. If $S=\emptyset$, then the composition $A^{-1}{M_\epsilon}A$ is a continuous bijection with the required properties and we are finished.
Otherwise, let $S_A=\{A(s)|s\in S\}$ and $S_A^*$ be the subset of $S_A$ whose elements lie on the segment $[-1,1]$. If $S_A\setminus S_A^*$ is not empty there exists a real number $k\geq1$ and an invertible linear transformation $B_k:x+iy\rightarrow x+iky\,$ s.t. after the transformation all of the transformed points of $S_A\setminus S_A^*$ lie outside the disc of radius $1$ (and if $S_A\setminus S_A^*=\emptyset$, we can continue by choosing $k=1$).
We can now find an appropriate $\epsilon$ such that none of the points of $S_{AB}=\{B_k(t)|t\in S_A\}$ lie in the angular ring $[1-\epsilon,1+\epsilon]$, and the composition $M = A^{-1}B_k^{-1}{M_\epsilon}B_kA$ fulfills all the necessary conditions.
With this lemma in hand, it is clear that if ${z_1,\dots,z_n}$ are the original vertex locations and ${z_1^*,\dots,z_n^*}$ are the corresponding target locations, for each pair $(z_i,z_i^*)$ there exists a continuous bijection which switches between $z_i$ and $z_i^*$ while leaving all the other locations unchanged, and therefore any composition of all of these bijections is a transformation of the original embedding to the target embedding.
