Moving Vertices to Make Drawings Plane

A straight-line drawing $\delta$ of a planar graph $G$ need not be plane, but can be made so by moving some of the vertices. Let shift$(G,\delta )$ denote the minimum number of vertices that need to be moved to turn $\delta$ into a plane drawing of $G$. We show that shift$(G,\delta )$ is NP-hard to compute and to approximate, and we give explicit bounds on shift$(G,\delta )$ when $G$ is a tree or a general planar graph. Our hardness results extend to 1BendPointSetEmbeddability, a well-known graph-drawing problem.