Retour à la page principale
Un commentaire ? E-mail:
Soient deux plongements Gamma et Gamma' de G dans le plan tels que les deux faces externes sont incidentes aux mêmes sommets de G, ceux-ci étant situés aux mêmes positions dans les deux plongements. L'objectif est alors de donner une construction algorithmique d'une isotopie, c'est-à-dire une famille continue de plongements Gamma_t, t entre 0 et 1, avec Gamma_0=Gamma et Gamma_1=Gamma'.
Notre approche du problème de calcul d'une isotopie repose sur l'idée physique suivante. Fixons les sommets extérieurs de Gamma, et remplaçons par la pensée les arêtes non incidentes à la face externe par des ressorts (de longueurs à vide nulles), les sommets intérieurs pouvant se déplacer en restant fixés à ces ressorts. Tutte a démontré que, dans des conditions raisonnables (graphe 3-connexe, complémentaire de la face externe convexe, constantes de raideur >0), l'équilibre du système physique ainsi créé constitue un plongement : les arêtes ne se croisent pas. Maintenant, si l'on modifie petit à petit les constantes de raideur des ressorts, l'équilibre se déplace ; on peut ainsi déformer le graphe.
Nous calculons, grâce à la correspondance de Maxwell-Cremona, des constantes de raideur de ressorts (stress) correspondant à l'équilibre Gamma (resp. Gamma'). Le problème est maintenant d'interpoler les deux familles de constantes de raideur pour passer de Gamma à Gamma', sans créer de croisements d'arêtes. Cela se fait sans difficulté par interpolation linéaire si tous les coefficients sont >0. Cependant, cette condition n'est pas toujours réalisable, et dans ce cas le problème n'est pas toujours résolu avec cette approche.