A polynomial bound for untangling geometric planar graphs
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 (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 vertices fixed.
|Keywords||Crossings, Geometric graphs, Untangling|
|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