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ε vertices fixed. We answer this question in the affirmative with ε = 1/4. The previous best known bound was. We also consider untangling geometric trees. It is known that every n-vertex geometric tree can be untangled while keeping at least vertices fixed, while the best upper bound was. We answer a question of Spillner and Wolff ( 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 vertices fixed.

Crossings, Geometric graphs, Untangling
Discrete and Computational Geometry
School of Computer Science

Bose, P, Dujmović, V, Hurtado, F. (Ferran), Langerman, S. (Stefan), Morin, P, & Wood, D. (2009). A polynomial bound for untangling geometric planar graphs. Discrete and Computational Geometry, 42(4), 570–585. doi:10.1007/s00454-008-9125-3