Triangulation canonique d'un graphe 3-connexe

Luca Castelli Aleardi (LIX, Ecole Polytechnique)

Résumé:

Les récents travaux dans le domaine de la compression de maillages ont été motivés par les nombreuses applications qui nécessitent des représentations compactes pour le stockage et la transmission de modèles 3D.

En particulier nous nous occupons de la compression sans perte de la connectivité de maillages polygonaux homéomorphes à une sphère. Nous proposons un algorithme de codage pour la transformation d'un maillage 3D polygonal en un maillage triangulaire, obtenant un codeur complet en combinant un codeur de maillages triangulaires.

Etant donné un graphe G planaire 3-connexe ayant e arêtes, nous introduisons un type spécial de triangulation T_G de G, basée sur les ordres canoniques de cette classe de graphes. Nous montrons comment reconstruire le graphe original en partant de sa triangulation canonique T_G, utilisant seulement les degrés des faces: cette phase de triangulation prend un temps linéaire et nécessite au plus e+o(e) bits. Notre codage canonique de la triangulation de G peut être combiné avec n'importe lequel codeur de triangulation afin d'obtenir un codeur complet de la connectivité d'un maillage polygonal de genre 0.