Personal tools
 

Untangling curves on surfaces via local moves

— filed under:

Hsien-Chih Chang, University of Illinois at Urbana-Champaign

What
  • Computer Science Seminar
When Wed, Jan 18, 2017
from 03:10 PM to 04:00 PM
Where Ritter Hall 115
Add event to calendar vCal
iCal
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.

« September 2017 »
September
SuMoTuWeThFrSa
12
3456789
10111213141516
17181920212223
24252627282930