Untangling planar graphs

Josef Cibulka

MFF

Abstract

Untangling is a process in which some vertices in a planar drawing of a graph are moved to obtain a straight-line planar drawing. The aim is to move as few vertices as possible. I will present an algorithm that untangles any drawing of the cycle graph C_n while keeping at least \Omega(n^{2/3}) vertices fixed. In the rest of the talk, I will sketch a proof of an upper bound on the number of fixed vertices in the worst case. For any given planar graph G, 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((n log n)^{2/3}) for all 3-vertex-connected planar graphs on n vertices.