Given a planar graph $G$, we consider drawings of $G$ in the plane where edges are represented by straight line segments (which possibly intersect). Such a drawing is specified by an injective embedding $pi$ of the vertex set of $G$ into the plane. We prove that a wheel graph $W_n$ admits a drawing $pi$ such that, if one wants to eliminate edge crossings by shifting vertices to new positions in the plane, then at most $(2+o(1))sqrt n$ of all $n$ vertices can stay fixed. Moreover, such a drawing $pi$ exists even if it is presupposed that the vertices occupy any prescribed set of points in the plane. Similar questions are discussed for other families of planar graphs.
تحميل البحث