The number of corner polyhedra graphs - Département d'informatique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2020

The number of corner polyhedra graphs

Résumé

Corner polyhedra were introduced by Eppstein and Mumford (2014) as the set of simply connected 3D polyhedra such that all vertices have non negative integer coordinates, edges are parallel to the coordinate axes and all vertices but one can be seen from infinity in the direction (1, 1, 1). These authors gave a remarkable characterization of the set of corner polyhedra graphs, that is graphs that can be skeleton of a corner polyhedron: as planar maps, they are the duals of some particular bipartite triangulations, which we call hereafter corner triangulations. In this paper we count corner polyhedral graphs by determining the generating function of the corner triangulations with respect to the number of vertices: we obtain an explicit rational expression for it in terms of the Catalan gen- erating function. We first show that this result can be derived using Tutte's classical compositional approach. Then, in order to explain the occurrence of the Catalan series we give a direct algebraic decomposition of corner triangu- lations: in particular we exhibit a family of almond triangulations that admit a recursive decomposition structurally equivalent to the decomposition of binary trees. Finally we sketch a direct bijection between binary trees and almond triangulations. Our combinatorial analysis yields a simpler alternative to the algorithm of Eppstein and Mumford for endowing a corner polyhedral graph with the cycle cover structure needed to realize it as a polyhedral graph.
Fichier principal
Vignette du fichier
final_63.pdf (406.58 Ko) Télécharger le fichier
Loading...

Dates et versions

hal-02173385 , version 1 (04-07-2019)

Identifiants

Citer

Clement Dervieux, Dominique Poulalhon, Gilles Schaeffer. The number of corner polyhedra graphs. 28-th International Conference on Formal Power Series and Algebraic Combinatorics, Simon Fraser University, Jul 2016, Vancouver, Canada. ⟨10.46298/dmtcs.6420⟩. ⟨hal-02173385⟩
33 Consultations
383 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More