4-8 juil. 2016 Vancouver, British Columbia (Canada)
The number of corner polyhedra graphs
Clement Dervieux  1  , Dominique Poulalhon  1  , Gilles Schaeffer  2  
1 : Institut de Recherche en Informatique Fondamentale  (IRIF)  -  Site web
Université Paris Diderot - Paris 7, Centre National de la Recherche Scientifique : UMR8243
Université Paris-Diderot – Paris 7 Case 7014 75205 PARIS Cedex 13 -  France
2 : Laboratoire dínformatique de l\'École polytechnique [Palaiseau]  (LIX)  -  Site web
Ecole Polytechnique, Centre National de la Recherche Scientifique : UMR7161
Route de Saclay 91128 PALAISEAU CEDEX -  France

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. 



  • Poster
Personnes connectées : 1