Before revision:  First we provide a stronger \Omega(n^2) lower bound when the  graph has two or more terminals, which follows from a quadratic lower bound on the number of homotopy moves in the annulus , described in a companion paper .
After revision:  First we provide a stronger \Omega(n^2) lower bound when the planar graph has two or more terminals, which follows from a quadratic lower bound on the number of homotopy moves in the annulus , described in a companion paper .