Untangling planar graphs from a specified vertex position - Hard cases

Abstract

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.

18 pages, 4 figures. Lemma 3.3 is corrected, several amendments are made throughout the paper

References in corpus (5)

• Untangling a Planar Graph
• A polynomial bound for untangling geometric planar graphs
• Untangling polygons and graphs
• Moving Vertices to Make Drawings Plane
• How Much Work Does It Take To Straighten a Plane Graph Out?

Cited by in corpus (3)

• How Much Work Does It Take To Straighten a Plane Graph Out?
• On collinear sets in straight line drawings
• Every Collinear Set in a Planar Graph Is Free