Technische Universität Berlin
Thursday, May 10 at 3:00 PM
Planar graphs are known to have contact representations of various types. The most prominent example is Koebe’s `kissing coins theorem’. Its rediscovery by Thurston lead to effective versions of the Riemann Mapping Theorem and motivated Schramm’s Monster Packing Theorem. Monster Packing implies the existence of contact representations of planar triangulations where each vertex v is represented by a homothetic copy of some smooth strictly-convex prototype P_v.
In this talk we present recent results concerning computable approximations of Schramm representations. For fixed K approximate P_v by an equiangular K-gon Q_v with horizontal basis. From Schramm’s work it follows that the given triangulation also has a contact representation with homothetic copies of these K-gons. Our approach starts by guessing a K-contact-structure, i.e., the combinatorial structure of a contact representation. From the combinatorial data, we build a system of linear equations whose variables correspond to lengths of boundary segments of the K-gons. If the system has a non-negative solution, this yields the intended contact representation. If the solution of the system contains negative variables, these can be used as sign-posts indicating how to change the K-contact-structure for another try.
In the case K=3 the K-contact-structures are Schnyder woods, and in the case K=4 they are transversal structures. As in these cases, for K>=5 the K-contact-structures of a fixed graph are in bijection to certain integral flows, and can be viewed as elements of a distributive lattice.
The procedure has been implemented. It computes the solution with few iterations.
Download presentation (password protected)