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.

Additional Metadata
Keywords Crossings, Geometric graphs, Untangling
Persistent URL
Journal Discrete and Computational Geometry
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