The Erdös-Nagy Theorem and its Ramifications

Given a simple polygon in the plane, a ip is de ned as follows: consider the convex hull of the polygon. If there are no pockets do not perform a ip. If there are pockets then reflect one pocket across its line of support of the polygon to obtain a new simple polygon. In 1934 Paul Erd}os conjectured that every simple polygon will become convex after a finite number of flips. The result was first proved by Bela Nagy in 1939. Since then it has been rediscovered many times in different contexts, apparently, with none of the authors aware of each other's work. The purpose of this paper is to bring to light this "hidden" work. We review the history of this problem, provide a simple elementary proof of the theorem and consider variants, generalizations and applications of interest in computational knot theory and molecular biology. We also uncover an incorrect "walk" algorithm in the knot theory literature and show howit can be xed with the Erdös-Nagy theorem and other more efficient methods. We close with several open problems