Untangling polygons and graphs

Details Untangling polygons and graphs Untangling polygons and graphs

2008-02-10

arxiv.org/abs/0802.1312v2

Discrete and Computational Geometry 43(2): 402-411 (2010)

Computer Science

Computational Geometry

11 pages, 3 figures

Scientific paper

10.1007/s00454-009-9150-x

Untangling is a process in which some vertices of a planar graph are moved to obtain a straight-line plane drawing. The aim is to move as few vertices as possible. We present an algorithm that untangles the cycle graph C_n while keeping at least \Omega(n^{2/3}) vertices fixed. For any graph G, we also present an upper bound on the number of fixed vertices in the worst case. The bound is a function of the number of vertices, maximum degree and diameter of G. One of its consequences is the upper bound O((n log n)^{2/3}) for all 3-vertex-connected planar graphs.

Affiliated with

Also associated with

No associations

Rating

Untangling polygons and 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 Untangling polygons and graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Untangling polygons and graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-295494