New Bounds on The Encoding of Planar Triangulations
Stefan Gumhold · 2000
Compact encodings of the connectivity of planar triangulations is a very important subject not only in graph theory but also in computer graphics. In 1962 Tutte determined the number of different planar triangulations. From his results follows that the encoding of the connectivity of planar triangulations with three border edges and vertices consumes in the asymptotic limit for � at least � � � � bits. Currently the best compression method with guaranteed upper bounds is based on the encoding of � �-Edgebreaker strings and consumes no more than �� � bits per vertex. In this report we improve these results to �� � bits per vertex. We also present a new coding scheme for the split indices in a different encoding method- the Cut-Border Machine. We describe an encoding with an upper bound of �� � bits per vertex. Finally, we introduce a Cut-Border data structure which allows for linear coding and decoding algorithms.