Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
Equiangular Polygon Contact Representations
verfasst von : Stefan Felsner, Hendrik Schrezenmaier, Raphael Steiner
Erschienen in: Graph-Theoretic Concepts in Computer Science
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
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\).
With this work we aim at 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
, 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.
, 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, in the case \(K=4\) they are transversal structures. As in these cases, for \({K \ge 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. The experiments involved graphs with up to one hundred vertices.