A polynomial bound for untangling geometric planar graphs

Details A polynomial bound for untangling geometric planar graphs A polynomial bound for untangling geometric planar graphs

2007-10-09

arxiv.org/abs/0710.1641v2

Discrete & Computational Geometry 42(4):570-585, 2009

Computer Science

Computational Geometry

14 pages, 7 figures

Scientific paper

10.1007/s00454-008-9125-3

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^\epsilon vertices fixed. We answer this question in the affirmative with \epsilon=1/4. The previous best known bound was \Omega((\log n / \log\log n)^{1/2}). We also consider untangling geometric trees. It is known that every n-vertex geometric tree can be untangled while keeping at least (n/3)^{1/2} vertices fixed, while the best upper bound was O(n\log n)^{2/3}. 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/2}-1) vertices fixed. Moreover, we improve the lower bound to (n/2)^{1/2}.

Affiliated with

Also associated with

No associations

Rating

A polynomial bound for untangling geometric planar graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A polynomial bound for untangling geometric planar graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A polynomial bound for untangling geometric planar graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-116192