To untangle a geometric graph means to move some of the vertices so that the resulting geometric graph has no crossings. Pach and Tardos (Discrete Comput. Geom. 28(4): 585-592, 2002) asked if every n-vertex geometric planar graph can be untangled while keeping at least n(epsilon) vertices fixed. We answer this question in the affirmative with epsilon = 1/4. The previous best known bound was Omega (root log n/log log n). We also consider untangling geometric trees. It is known that every n-vertex geometric tree can be untangled while keeping at least Omega(root n) vertices fixed, while the best upper bound was O((n log n)(2/3)). We answer a question of Spillner and Wolff (http://arxiv.org/abs/0709.0170) by closing this gap for untangling trees. In particular, we show that for infinitely many values of n, there is an n-vertex geometric tree that cannot be untangled while keeping more than 3(root n - 1) vertices fixed.
展开▼
