A Bijection for Essentially 4-Connected Toroidal Triangulations - Optimisation Combinatoire Accéder directement au contenu
Article Dans Une Revue The Electronic Journal of Combinatorics Année : 2019

A Bijection for Essentially 4-Connected Toroidal Triangulations

Nicolas Bonichon
Benjamin Lévêque

Résumé

Transversal structures (also known as regular edge labelings) are combinatorial structures defined over 4-connected plane triangulations with quadrangular outer-face. They have been intensively studied and used for many applications (drawing algorithm, random generation, enumeration, ...). In this paper we introduce and study a generalization of these objects for the toroidal case. Contrary to what happens in the plane, the set of toroidal transversal structures of a given toroidal triangulation is partitioned into several distributive lattices. We exhibit a subset of toroidal transversal structures, called balanced, and show that it forms a single distributive lattice. Then, using the minimal element of the lattice, we are able to enumerate bijectively essentially 4-connected toroidal triangulations.
Fichier principal
Vignette du fichier
2018-12-13-Revision-EJC.pdf (709.29 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02044281 , version 1 (02-10-2020)

Identifiants

Citer

Nicolas Bonichon, Benjamin Lévêque. A Bijection for Essentially 4-Connected Toroidal Triangulations. The Electronic Journal of Combinatorics, 2019, 26 (1), pp.P1.13. ⟨10.37236/7897⟩. ⟨hal-02044281⟩
37 Consultations
35 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More