Untangling a Planar Graph

Abstract

We show that it is NP-hard to compute and to approximate the minimum number of vertices that need to be moved to obtain a noncrossing drawing of a planar graph from a given plane straight-line drawing.

Keywords

• Untangling
• Planar
• Graph