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.