%0 Journal Article
%T Untangling planar graphs from a specified vertex position - Hard cases
%A Mihyun Kang
%A Oleg Pikhurko
%A Alexander Ravsky
%A Mathias Schacht
%A Oleg Verbitsky
%J Computer Science
%D 2008
%I arXiv
%R 10.1016/j.dam.2011.01.011
%X 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.
%U http://arxiv.org/abs/0803.0858v5