Graph Coding and Connectivity Compression

Martin Isenburg and Jack Snoeyink
University of California, Berkeley, CA 94720-3840, USA

Abstract

This paper looks at the theoretic roots of current connectivity compression schemes to establish a visual framework within which the differences and similarities of various scheme become intuitive. We show the intimate connections between the classic work on planar graph coding by Turan and recent schemes, such as Edgebreaker, Face Fixer, and the optimal coding by method of Poulalhon and Schaefer.
Other results are an elegant method for reverse decoding of meshes encoded with Poulalhon and Schaefer's optimal coder, and the insight that the classic Keeler and Westbrook method and the Edgebreaker scheme are really the same algorithm for the case of encoding planar triangulations.