Carte combinatoire

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[1]. La première expression formelle des cartes a été donnée par Alain Jacques sous le nom de constellation[2] - [3] mais le concept a déjà été utilisé auparavant de manière intensive, sous le nom de rotation, par Gerhard Ringel[4] et John William Theodore Youngs dans leur célèbre solution au problème de coloration de cartes de Heawood[5]. C'est la dénomination carte combinatoire (« combinatorial map » 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 d'incidence et d'adjacence entre ces cellules. Lorsque toutes les cellules représentées sont des simplexes, un complexe simplicial peut être employé, mais dans le cas général on utilise des modèles de topologique cellulaire comme les cartes combinatoires ou les cartes généralisées.

Les premiers travaux sur les cartes combinatoires[3] - [6] développent une représentation de graphes sur des surfaces qui comprennent en particulier les graphes planaires : Une carte combinatoire de dimension 2 est une structure ${\displaystyle (B,\sigma ,\alpha )}$, où

• ${\displaystyle B}$ est un ensemble fini dont les éléments sont appelés les brins
• ${\displaystyle \sigma }$ est une permutation sur ${\displaystyle B}$;
• ${\displaystyle \alpha }$ est une involution sans point fixe sur ${\displaystyle B}$.

Intuitivement, une telle carte correspond à un graphe dessiné sur une surface, où chaque arête est subdivisée en deux brins (parfois aussi appelées « demi-arêtes »). La permutation ${\displaystyle \sigma }$ donne, pour chaque brin, le brin suivant en tournant autour du sommet dans le sens positif ; l'autre permutation ${\displaystyle \alpha }$ donne, pour chaque brin, le brin opposé de la même arête. Les cycles de la permutation ${\displaystyle \alpha }$ permettent de retrouver les arêtes, et les cycles de ${\displaystyle \sigma }$ les sommets du graphe. On définit une troisième permutation ${\displaystyle \varphi }$ par

${\displaystyle \varphi =\sigma \circ \alpha }$.

Cette permutation donne, pour chaque brin, le brin suivant sur la même face ; ainsi, les cycles de ${\displaystyle \varphi }$ s'identifient aux faces de la représentation. Selon les cas, on peut utiliser la représentation ${\displaystyle (B,\sigma ,\alpha )}$ ou ${\displaystyle (B,\varphi ,\alpha )}$ qui sont équivalentes puisque ${\displaystyle \sigma =\varphi \circ \alpha }$. Les deux représentations sont duales au sens qu'elles échangent sommets et faces.

Une carte est planaire si et seulement si la somme du nombre de sommets et du nombre de faces est égale au nombre d'arêtes plus 2.

Une carte planaire est un plongement d’un graphe connexe et planaire sur la sphère, considéré à déformation continue près. Bien que définies sur la sphère, on préfère dessiner les cartes dans le plan. Une des faces se trouve alors privilégiée, la face externe. Dans l'exemple ci-dessous, la face externe est (1 3 18 16 14 12 10).

• Exemple de carte planaire
• 
  Graphe planaire
• 
  Carte planaire ${\displaystyle (B,\sigma ,\alpha )}$ par sommets et arêtes
• 
  Carte planaire ${\displaystyle (B,\varphi ,\alpha )}$ par faces et arêtes

Les trois permutations

${\displaystyle B}$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
${\displaystyle \alpha }$	2	1	4	3	6	5	8	7	10	9	12	11	14	13	16	15	18	17
${\displaystyle \sigma }$	7	3	2	18	4	15	9	6	1	11	10	13	12	8	14	17	16	5
${\displaystyle \varphi }$	3	7	18	2	15	4	6	9	11	1	13	10	8	12	17	14	5	16

Le comptage des cartes planaires remonte à des travaux de Tutte[7] - [8]. L'approche par la combinatoire bijective a commencé au début des années 1980, développée surtout par l'école bordelaise de combinatoire[9] - [10]. Une illustration en est le dénombrement de cartes planaires « tétravalentes » (où chaque sommet est de degré 4) à n sommets : ce nombre est[11]

${\displaystyle m_{n}=2{\frac {3^{n}}{(n+1)(n+2)}}{\binom {2n}{n}}}$

Cette formule suggère une bijection avec une famille d'arbres ; c'est ce genre de bijections qui est établie, pour montrer aussi que les séries génératrices de ces suites de nombres sont algébriques. D'autres applications ont été données[12].

La définition d'une carte combinatoire s'étend à toute dimension[13] - [14] : Une carte combinatoire de dimension ${\displaystyle n}$ est une structure ${\displaystyle (B,\beta _{1},\dots ,\beta _{n})}$, où

• ${\displaystyle B}$ est un ensemble fini de brins;
• ${\displaystyle \beta _{1}}$ est une permutation sur ${\displaystyle B}$;
• ${\displaystyle \beta _{2},\ldots ,\beta _{n}}$ sont des involutions sur ${\displaystyle B}$;
• ${\displaystyle \beta _{i}\circ \beta _{j}}$ est une involution pour tout ${\displaystyle i,j}$ vérifiant ${\displaystyle 2\leq i+2\leq j}$.

Une carte combinatoire de dimension n représente une subdivision d'un espace fermé orientable de dimension n. Un brin est un élément abstrait qui sert à définir les bijections. Les contraintes de la dernière condition garantissent la cohérence topologique de l'objet représenté : une carte combinatoire représente une quasi-variété.

• Boundary representation
• Carte généralisée
• Doubly connected edge list (en)
• Quad-edge data structure (en)
• Rotation system (en)
• Complexe simplicial
• Simplexe
• Arête ailée (en)

• Combinatorial maps in CGAL, the Computational Geometry Algorithms Library:
• « Combinatorial maps », CGAL, the Computational Geometry Algorithms Library (consulté en octobre 2011)
• Combinatorial maps in CGoGN, Combinatorial and Geometric modeling with Generic N-dimensional Maps