Back to Videos
This is a video about Untangling Planar Curves and Planar Graphs

Untangling Planar Curves and Planar Graphs

May 19, 2016
MBI
Presenters: Jeff Erickson
Length: 51 minutes 29 seconds

Watch Video 

Abstract

Any generic closed curve in the plane can be transformed into a simple closed curve by

a finite sequence of local transformations called homotopy moves. We prove that simplifying a

planar curve with n self-crossings requires Theta(n^{3/2}) homotopy moves in the worst case.

The best bounds previously known were a 100-year-old O(n^2) upper bound due to Steinitz and

the trivial Omega(n) lower bound. Our lower bound also implies that Omega(n^{3/2}) degree-1

reductions, series-parallel reductions, and Delta-Y transformations are required to reduce any

planar graph with treewidth Omega(sqrt{n}) to a single edge, matching known upper bounds for

rectangular and cylindrical grid graphs. Finally, we prove that Omega(n^2) homotopy moves are

required in the worst case to transform one non-contractible closed curve on the torus to another;

this lower bound is tight if the curve is homotopic to an embedding.