Untangling polygons and graphs

Untangling is a process in which some vertices of a plane graph are moved to obtain a straight-line plane drawing. The aim is to move as few vertices as possible. We present an algorithm that untangles the cycle graph Cn while keeping at least Ω(n2/3) vertices fixed. For any graph G, we also present an upper bound for the number of fixed vertices in the worst case. The bound is a function of the number of vertices, maximum degree and diameter of G. One of its consequences is the upper bound O((nlogn)2/3) for all 3-vertex-connected planar graphs.