HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Canonical Triangulation of a Graph, with a Coding Application

Luca Castelli Aleardi 1 Olivier Devillers
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : For compression of 3D meshes, we propose an algorithm to encode the transformation of a polygonal mesh into a triangular mesh, getting a full coder by combination with a triangular coder. In this way, we benefit of the possibility of choosing a triangular coder relevant for a particular kind of mesh. Let $G$ be a $3$-connected simple planar graph with $e$ edges. We introduce a special type of triangulation $T_G$ of $G$, based on the canonical orderings of this class of graphs. We show how to reconstruct the original graph starting from its canonical triangulation $T_G$, using only the face degrees of $G$: this detriangulation phase takes linear time and requires at most $e+o(e)$ bits. Our canonical coding of the detriangulation of $G$ can be combined with any triangulation coder to obtain a full coder of the connectivity of any genus $0$ polygonal mesh.
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 9:34:24 PM
Last modification on : Friday, February 4, 2022 - 3:19:35 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:52:21 PM


  • HAL Id : inria-00070765, version 1



Luca Castelli Aleardi, Olivier Devillers. Canonical Triangulation of a Graph, with a Coding Application. RR-5231, INRIA. 2004, pp.24. ⟨inria-00070765⟩



Record views


Files downloads