Electrical Reduction, Homotopy Moves, and Defect

We prove the first nontrivial worst-case lower bounds for two closely related problems. First, Ω(n^3/2) degree-1 reductions, series-parallel reductions, and ΔY transformations are required in the worst case to reduce an n-vertex plane graph to a single vertex or edge. The lower bound is achieved by any planar graph with treewidth Θ(√n). Second, Ω(n^3/2) homotopy moves are required in the worst case to reduce a closed curve in the plane with n self-intersection points to a simple closed curve. For both problems, the best upper bound known is O(n²), and the only lower bound previously known was the trivial Ω(n).

The first lower bound follows from the second using medial graph techniques ultimately due to Steinitz, together with more recent arguments of Noble and Welsh. The lower bound on homotopy moves follows from an observation by Haiyashi et al. that the standard projections of certain torus knots have large defect, a topological invariant of generic closed curves introduced by Aicardi and Arnold. Finally, we prove that every closed curve in the plane with n crossings has defect O(n^3/2), which implies that better lower bounds for our algorithmic problems will require different techniques.

Electrical reduction, homotopy moves, and defect