Untangling planar graphs from a specified vertex positionHard cases
Given a planar graph G G , we consider drawings of G G 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 G G into the plane. Let fix ( G , ? ) be the maximum integer k k such that there exists a crossing-free redrawing ?? ? ? of G G which keeps k k vertices fixed, i.e., there exist k k vertices v1,,vk v 1 ,  , v k of G G such that ?(vi)=??(vi) ? ( v i ) = ? ? ( v i ) for i=1,,k i = 1 ,  , k . Given a set of points X X , let fix X ( G ) denote the value of fix ( G , ? ) minimized over ? ? locating the vertices of G G on X X . The absolute minimum of fix ( G , ? ) is denoted by fix ( G ) . For the wheel graph Wn W n , we prove that fix X ( W n ) ? ( 2 + o ( 1 ) ) n for every X X . With a somewhat worse constant factor this is also true for the fan graph Fn F n . 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 fix X ( G ) is always attainable by a collinear X X .
planar graphs combinatorial geometry graph drawing untangling problem