Laboratoire d'informatique de l'École polytechnique

Exposé par Hendrik Schrezenmaier: «Polygon contact representations»

Speaker: Hendrik Schrezenmaier
Location: BigBlueButton
Date: Mer. 6 mai. 2020, 10h30-11h30

La prochaine séance du séminaire Combi du Plateau de Saclay aura lieu ce mercredi 6 mai à 10h30. Nous aurons le plaisir d’écouter Hendrik Schrezenmaier (TU Berlin).

L’exposé se tiendra en ligne par BigBlueButton.

Le programme du séminaire est disponible ici :

Résumé : 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.