Carte combinatoire

Une carte combinatoire est un objet combinatoire qui intervient dans la modélisation de structures topologiques subdivisées en objets. La version la plus simple en est la carte planaire, structure combinatoire pour la représentation de graphes planaires dans le plan. Le concept de carte combinatoire a été introduit de manière informelle au début des années 1960 par Jack Edmonds pour la modélisation de surfaces polyédriques. La première expression formelle des cartes a été donnée par Alain Jacques sous le nom de constellation mais le concept a déjà été utilisé auparavant de manière intensive, sous le nom de rotation, par Gerhard Ringel et John William Theodore Youngs dans leur célèbre solution au problème de coloration de cartes de Heawood. C'est la dénomination carte combinatoire ( en anglais) qui est utilisée couramment. Le concept a été étendu pour pouvoir représenter des objets subdivisés orientables en dimension supérieure. Les cartes combinatoires sont utilisées en tant que structures de données efficaces pour la représentation et le traitement d'images, et en modélisation géométrique. En infographie, ce modèle est appelé B-Rep model puisqu'il représente les objets par leur bord. Le modèle est lié aux complexes simpliciaux et à la topologie combinatoire. On peut étendre les cartes combinatoires à des cartes dites généralisées qui permettent aussi de représenter des objets non orientables comme le ruban de Möbius ou la bouteille de Klein. Diverses applications requièrent une structure de données qui permet de représenter les subdivisions d'un objet. Par exemple, un objet en 2 dimensions peut être décomposé en sommets (cellules de dimension 0), arêtes (cellules de dimension 1), et faces (cellules de dimension 2). De plus, il est souvent nécessaire de représenter les relations de voisinage entre ces cellules. L'objectif est décrire toutes les cellules de la subdivision, et de plus toutes les relations dincidence et dadjacence entre ces cellules.