D.E.A. work at Groningen University (The Netherlands).
Isotopies of planar graphs with applications to morphing.

Summary

Let G be a planar graph. An isotopy of G is a deformation of an embedding of G into another embedding. Our study of isotopies is initially motivated by applications to morphing.

Let Gamma and Gamma' be two embeddings of G into the plane such that both external faces are incident to the same vertices of G, these vertices being located at the same positions in both embeddings. The goal is now to compute an isotopy, that is, a continuous family of embeddings Gamma_t, t between 0 and 1, with Gamma_0=Gamma and Gamma_1=Gamma'.

Our strategy to compute an isotopy relies on the following physical idea. Fix the exterior vertices of Gamma, and imagine you replace the edges which are non-incident to the exterior face by springs (which have lengths zero when there is no force on them), 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 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.

We compute, using Maxwell-Cremona correspondence, rigidity constants of springs (stress) for the initial (Gamma) and final (Gamma') states. The problem is now to interpolate both families of rigidity constants to go from Gamma to Gamma' without introducing crossings. This is easy by linear interpolation of the weights if all coefficients are >0. However, this condition is not always realized, and in this case the problem is not always solved with this approach.

Details

This worked has been achieved from 2nd april to 13th july 2000, at the University of Groningen (The Netherlands), under the direction of Gert Vegter in collaboration with Michel Pocchiola. Among other things, you will find in the report a full proof (in English) of Tutte's barycentric map theorem.

The report [mainly French] is available (ps.gz, pdf, bib)

Back to main page

A comment? E-mail: eric colin de verdiere uu ens fr (replace space by dot and uu by @)