Tutte's Barycentric Method applied to Isotopies
Eric Colin de Verdiere
An isotopy of a planar graph G is a continuous family of embeddings of G.
We will describe a method for constructing isotopies of planar graphs with
fixed boundary, initially motivated by applications to deformations and
morphing, and relying on a theorem by Tutte to build embeddings of planar
graphs. Then we study the analogous of these methods to three dimensions.
Our strategy to compute an isotopy relies on the following physical idea.
Fix the exterior vertices of an embedding of G, and imagine you replace
the edges which are non-incident to the exterior face by springs, the
interior vertices remaining fixed to these springs. Tutte showed that,
under reasonable assumptions (3-connected graph, the complementary of the
exterior face being convex, rigidity constants >0), the equilibrium state
of this physical system is an embedding: no crossings occur.
Now, if you slightly modify the rigidity constants of the springs, the
equilibrium moves; it is possible to deform the graph in this way.
Considering both embeddings of G (with the same boundary) between which an
isotopy has to be built, we have to view them as equilibrium states of two
such physical systems, and to interpolate linearly the barycentric
coefficients.
Finally, we study the same isotopy problem in three dimensions, and show
that things are more complicated: there exist two embeddings of a
3-dimensional simplicial complex with the same boundary which are
combinatorially equivalent but for which there exists no isotopy from one
to the other. In fact, the analogous of Tutte's theorem in 3D is false.
Paper available at http://www.di.ens.fr/~colin/textes/cccg01-long.ps.gz