ELA, Volume 9, pp. 197-254, September 2002, abstract.
Iterations of Concave Maps, the Perron-Frobenius
Theory and Applications to Circle Packings
Ronen Peretz
The theory of pseudo circle packings is developed.
It generalizes the theory of circle packings. It
allows the realization of almost any graph embedding
by a geometric structure of circles. The corresponding
Thurston's relaxation mapping is defined and is used
to prove the existence and the rigidity of the pseudo
circle packing. It is shown that iterates of this
mapping, starting from an arbitrary point, converge to
its unique positive fixed point. The coordinates of
this fixed point give the radii of the packing. A key
property of the relaxation mapping is its superadditivity.
The proof of that is reduced to show that a certain real
polynomial in four variables and of degree 20 is always
nonnegative. This in turn is proved by using recently
developed algorithms from real algebraic geometry.
Another important ingredient in the development of the
theory is the use of nonnegative matrices and the
corresponding Perron-Frobenius theory.