Moving Vertices to Make Drawings Plane

Xavier Goaoc, Jan Kratochvil, Yoshio Okamoto +2

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…