A compact encoding of plane triangulations with efficient query supports

In this paper we present a coding scheme for plane triangulations. The coding scheme is very simple, and needs only 6n bits for each plane triangulation with n vertices. Also with additional o(n) bits it supports adjacency, degree and clockwise neighbour queries in constant time. Our scheme is based on a realizer of a plane triangulation. The best known algorithm needs only 4.35n+o(n) bits for each plane triangulation. Our algorithm is simple and needs 6n+o(n) bits for each plane triangulation.