Untangling planar graphs from a specified vertex position—Hard cases

Given a planar graph GG, we consider drawings of GG in the plane where edges are represented by straight line segments (which possibly intersect). Such a drawing is specified by an injective embedding ππ of the vertex set of GG into the plane. Let fix(G,π) be the maximum integer kk such that there exists a crossing-free redrawing π′π′ of GG which keeps kk vertices fixed, i.e., there exist kk vertices v1,…,vkv1,…,vk of GG such that π(vi)=π′(vi)π(vi)=π′(vi) for i=1,…,ki=1,…,k. Given a set of points XX, let fixX(G) denote the value of fix(G,π) minimized over ππ locating the vertices of GG on XX. The absolute minimum of fix(G,π) is denoted by fix(G).For the wheel graph WnWn, we prove that fixX(Wn)≤(2+o(1))n for every XX. With a somewhat worse constant factor this is also true for the fan graph FnFn. We inspect also other graphs for which it is known that fix(G)=O(n).We also show that the minimum value fix(G) of the parameter fixX(G) is always attainable by a collinear XX.