Untangling a Polygon

Pach, János and Tardos, Gábor (2002) Untangling a Polygon. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001, Vienna, Austria , pp. 154-161 (Official URL: http://dx.doi.org/10.1007/3-540-45848-4_13).

Full text not available from this repository.

Abstract

The following problem was raised by M. Watanabe. Let P be a self-intersecting closed polygon with n vertices in general position. How manys steps does it take to untangle P, i.e., to turn it into a simple polygon, if in each step we can arbitrarily relocate one of its vertices. It is shown that in some cases one has to move all but at most O((n log n)2/3) vertices. On the other hand, every polygon $P$ can be untangled in at most n − Ω(√n) steps. Some related questions are also considered.

Item Type:Conference Paper
Additional Information:10.1007/3-540-45848-4_13
Classifications:Z Theory > Z.250 Geometry
G Algorithms and Complexity > G.560 Geometry
ID Code:508

Repository Staff Only: item control page

References

Paul Erdös and G. Szekeres. A combinatorial problem in geometry. Compositio Mathematica 2(1935), 463-470.

J. Pach, F. Shahrokhi, and M. Szegedy. Applications of the crossing number. Algorithmica 16 (1996), 111-117. (Special Issue on Graph Drawing, edited by G. Di Battista and R. Tamassia).

J. Pach and R. Wenger. Embedding planar graphs with fixed vertex locations. In S. H. Whitesides, editor, Graph Drawing (Proc. GD '98), volume 1547 of Lecture Notes Comput. Sci., pages 263-274. Springer-Verlag, 1998.

Sýkora, O., Vrt'o, I. On VLSI layouts of the star graph and related networks. Integration, The VLSI journal 17 (1994), 83-93.