Tutte's Barycenter Method applied to Isotopies

Éric Colin de Verdière, Michel Pocchiola, and Gert Vegter. Tutte's Barycenter Method applied to Isotopies. Computational Geometry: Theory and Applications, vol. 26, no 1, pp. 81-97, 2003.

This page aims at:

  • giving the data of two examples for which the method described in Section 2 fails;
  • giving 3-dimensional coordinates for Starbird's example, as described in Section 3.

    • Two examples for which the method of Section 3 fails

    We define below two embeddings of triangulated planar graphs. For each of these embeddings, we compute a (non-necessarily positive) equilibrium stress using the lift z=x^2+y^2. We then try to get an isotopy using linear interpolation between this stress and the stress where all weights corresponding to an edge equal 1. The following examples show that this method does not always yield an isotopy. These examples have been found by generating randomly triangulated embeddings and detecting planarity failure (program in C++ using the LEDA library and Numerical Recipes), then checking the result by exact calculations using Mathematica.
    Here is the format of the data: each line corresponds to a vertex of the embedding and contains successively the number of the vertex, its coordinates x and y, and the list of its neighbors.

    Our minimal example

    In this counter-example, the situation is very close to a degeneracy. One can check by calculation the planarity of the initial embedding and the non-planarity at some stages of the process. There are 4 exterior vertices and 2 interior vertices.

    1 -500 900 2 5 6 4

    2 -850 900 1 3 5

    3 -950 -900 4 6 5 2

    4 0 -400 1 6 3

    5 -900 -699 6 1 2 3

    6 -800 -300 1 5 3 4

    The example given in the manuscript

    5 exterior vertices, 3 interior vertices.

    1 -681.67 314.31 5 2 8 6

    2 -938.19 -391.67 7 8 1 3

    3 419.75 -833.89 4 8 7 2

    4 841.39 52.42 5 6 8 3

    5 712.91 332.73 1 6 4

    6 733.43 99.34 5 1 8 4

    7 128.62 38.94 8 2 3

    8 277.47 156.82 1 2 7 3 4 6

    An example which gives an isotopy, as in the most common case

    Three-dimensional coordinates for Starbird's example

    The initial and final embeddings of the graph C are available in OOGL (vect) format, to be viewed for example using Geomview (these two files are commented and thus also human-readable).

    Last modified: Thu Feb 27 17:36:23 MET 2003