\input zb-basic
\input zb-ioport
\iteman{io-port 05252757}
\itemau{Yamanaka, Katsuhisa; Nakano, Shin-ichi}
\itemti{A compact encoding of plane triangulations with efficient query supports (extended abstract).}
\itemso{Nakano, Shin-ichi (ed.) et al., WALCOM: Algorithms and computation. Second international workshop, WALCOM 2008, Dhaka, Bangladesh, February 7--8, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-77890-5/pbk). Lecture Notes in Computer Science 4921, 120-131 (2008).}
\itemab
Summary: In this paper we give 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, however, within $o(n)$ bits it needs to store a complete list of all possible triangulations having at most $(\log n)/4$ nodes, while our algorithm is simple and does not need such a list. The second best known algorithm needs $2m + (5 + 1/k)n + o(m + n)$ bits for each (general) plane graph with $m$ edges and $7n + o(n)$ bits for each plane triangulation, while our algorithm needs only $6n + o(n)$ bits for each plane triangulation.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{doi:10.1007/978-3-540-77891-2\_12}
\end