A polynomial bound for untangling geometric planar graphs

الأصل · EN

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., 2002] asked if every n-vertex geometric planar graph can be untangled while keeping at least nεvertices fixed. We answer this question in the affirmative with ε=1/4. The previous best known bound was Ω((n / n)¹/²). We also consider untangling geometric trees. It is known that every n-vertex geometric tree can be untangled while keeping at least (n/3)¹/² vertices fixed, while the best upper bound was O(n n)²/³. We answer a question of Spillner and Wolff [arXiv:0709.0170 2007] 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(n¹/²-1) vertices fixed. Moreover, we improve the lower bound to (n/2)¹/².