Untangling Polygons and Graphs

Untangling Polygons and Graphs,10.1007/s00454-009-9150-x,Discrete & Computational Geometry,Josef Cibulka

Untangling Polygons and Graphs   (Citations: 1)
BibTex | RIS | RefWorks Download
Untangling is a process in which some vertices in a drawing 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 Ω(n 2/3) vertices fixed. For any connected 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 consequence is that every 3-connected planar graph has a drawing δ such that at most O((nlog n)2/3) vertices are fixed in every untangling of δ.
Journal: Discrete & Computational Geometry - DCG , vol. 43, no. 2, pp. 402-411, 2010
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: