Any continuous deformation of one closed curve to another on
the same surface can be decomposed into a finite sequence of local
transformations called *homotopy moves*. We are interested in the
number of homotopy moves required to simplify a generic closed curve
with n self-crossings as much as possible on an arbitrary surface. In
the plane, an O(n^2) upper bound is implicit in the classical work of
Steinitz on polyhedra; a later result of Hass and Scott extended this
upper bound to contractible curves on arbitrary surfaces.

*Electrical transformations*
--- the collection of degree-1 reductions, series-parallel reductions,
and ∆Y transformations --- was studied intensively due to its use in
optimization problems on planar graphs. Again we are interested in the
number of electrical transformations required to reduce a plane graph
with n vertices as much as possible. Using arguments of Noble and
Welsh, we can relate the number of electrical transformations required
to reduce a plane graph to the number of homotopy moves required to
simplify its medial graph, viewed as curves embedded in the plane. A
major open problem due to Feo and Provan is whether O(n^{3/2})
electrical transformations are always sufficient.

In
this talk we will start by surveying the classical results on these two
closely related problems, including the bigon reduction approach by
Steinitz, the face-depth potential method by Feo and Provan, and the
grid-minor approach by Truemper. Then we will briefly describe the
high-level idea of our new O(n^{3/2}) upper bound on the number of
homotopy moves required to simplify a plane curve. On the lower bound
side, we will prove that Ω(n^{3/2}) moves are sometimes necessary by
introducing a topological invariant of generic closed curves, called
defect, first defined by Aicardi and Arnold. Finally, we sketch a proof
that simplifying a contractible curve in the annulus --- and therefore
in any surface with nonpositive Euler characteristic --- requires Ω(n^2)
homotopy moves. The same lower bound extends to reducing plane graphs
with two terminals using facial electrical transformations, which
disproves the Feo and Provan conjecture in a restricted setting.

If
time allows, we will also discuss some generalizations to the problems,
including multicurves, non-facial local moves, bigon structures of
curves in surfaces, and relation to random knot theory.

This
is a joint work with Jeff Erickson. Some of the results are published
in our previous SoCG paper and its earlier preprint; the newer results
can be found in our upcoming paper.