Tightening curves on surfaces via local moves

We prove new upper and lower bounds on the number of homotopy moves required to tighten a closed curve on a compact orientable surface (with or without boundary) as much as possible. First, we prove that Ω( n 2 ) moves are required in the worst case to tighten a contractible closed curve on a surface with non-positive Euler characteristic, where n is the number of self-intersection points. Results of Hass and Scott imply a matching 0 ( n 2 ) upper bound for contractible curves on orientable surfaces. Second, we prove that any closed curve on any orientable surface can be tightened as much as possible using at most 0 ( n 4 ) homotopy moves. Except for a few special cases, only naive exponential upper bounds were previously known for this problem.