Unwinding annular curves and electrically reducing planar networks

With Hsien-Chih Chang*.

To appear in Abstracts of the Computational Geometry: Young Researchers Forum, 2017.

Simplifying a contractible curve in the annulus, and therefore in any surface that has a covering space homeomorphic to an annulus, requires Ω(n²) homotopy moves in the worst case. It follows that Ω(n²) facial electrical transformations are required in the worst case to reduce a plane graph with two terminals as much as possible. Both lower bounds match known upper bounds up to constant factors.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 25 May 2017