Polygon contact representations
Time: 10:30 -- Location: à distance
En ligne
In a contact representation of a planar graph, the vertices of the graph are represented by objects in the plane with disjoint interiors and the edges correspond to touchings of these objects. The combinatorics of contact representations of planar triangulations with homothetic triangles are known to be described by Schnyder woods and the combinatorics of contact representations with axis-aligned rectangles are known to be described by transversal structures. In this talk, we will introduce a generalization of these structures that is suitable to describe the combinatorics of contact representations with regular K-gons for arbitrary K>=5.
Afterwards, we will see how these structures can be used for the computation of the contact representations and for proving their existence. The idea of these methods is to associate a system of linear equations with each K-contact structure and to search for a K-contact structure whose system of equations has a non-negative solution. Then this solution encodes the contact representation. The way this search is done is quite beautiful and produces nice pictures.
This is joint work with Stefan Felsner and Raphael Steiner.