Untangling Planar Graphs and Curves by Staying Positive

Any generic planar closed curve with n crossings can be turned into a simple closed curve by applying O(n 3/2 ) homotopy moves without ever increasing the number of self-crossings; this improves over the O(n 2 ) upper bound from Steinitz [Ency. Math. Wiss. III 1916], and matches the best lower bound. We prove the existence of a positive move that decreases the depth-sum potential at every step. Using similar techniques, we show that any 2-terminal plane graph with n vertices can be reduced to a single edge between the terminals using O(n 3/2 ) electrical transformations, consisting of degree-1 reductions, series-parallel reductions, and ∆Y-transformations; this proves a conjecture of Feo and Provan that was open for more than 30 years.