The invention relates to the valence-based encoding of connectivity data of a 3D mesh. A command is generated for each free edge of each vertex traversed and describes the vertex at the other end of the edge. The obtained list of commands is encoded by mapping each command onto a symbol. A mapping table associating commands with a set of respective consecutive numeral symbols is used. The list of symbols is then encoded, separately to the encoding of parameters of the commands. A joint encoding may be used to encode two or more consecutive symbols using a single coding word. A look-up table may be used based on the valence values intrinsically defined by each symbol, in order to give priority to the most frequent valence values (usually around 6). Prior to generating the commands, a vertex may be added to the 3D mesh to artificially fill any hole therein.