Electrical Reduction, Homotopy Moves, and Defect

We prove the first nontrivial worst-case lower bounds for two closely related problems. First, $Ω(n^{3/2})$ degree-1 reductions, series-parallel reductions, and $Δ$Y transformations are required in the worst case to reduce an $n$-vertex plane graph to a single vertex or edge. The lower bound is achieved by any planar graph with treewidth $Θ(\sqrt{n})$. Second, $Ω(n^{3/2})$ homotopy moves are required in the worst case to reduce a closed curve in the plane with $n$ self-intersection points to a simple closed curve. For both problems, the best upper bound known is $O(n^2)$, and the only lower bound previously known was the trivial $Ω(n)$. The first lower bound follows from the second using medial graph techniques ultimately due to Steinitz, together with more recent arguments of Noble and Welsh [J. Graph Theory 2000]. The lower bound on homotopy moves follows from an observation by Haiyashi et al. [J. Knot Theory Ramif. 2012] that the standard projections of certain torus knots have large defect, a topological invariant of generic closed curves introduced by Aicardi and Arnold. Finally, we prove that every closed curve in the plane with $n$ crossings has defect $O(n^{3/2})$, which implies that better lower bounds for our algorithmic problems will require different techniques.

No reviews yet.

No comments yet.