کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421256 | 684171 | 2011 | 11 صفحه PDF | دانلود رایگان |
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.
Journal: Discrete Applied Mathematics - Volume 159, Issue 8, 28 April 2011, Pages 789–799