Abstract
Untangling is a process in which some vertices in a drawing of a planar 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 while keeping \Omega(n^{2/3}) vertices fixed. For any connected graph G, we also present an upper bound on 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.