On the succinct representation of graphs (Q800734)

Let \({\mathcal G}_ be\) a class of (labeled or unlabeled) graphs and \({\mathcal G}_ n\) be the class of graphs in \({\mathcal G}\) having n vertices. The problem discussed is the following: find a representation (or encoding) of graphs in \({\mathcal G}\) which is succinct (i.e. the length of the encoding of \(G\in {\mathcal G}_ n\) is not too large compared with the lower bound \(\log_ 2| {\mathcal G}_ n|)\) and efficiently (e.g. polynomial time) computable. The paper considers the case of planar graphs. An encoding using at most 12n bits is given for the unlabeled case and (improving a result of \textit{A. Itai} and \textit{M. Rodeh} [Acta Inf. 17, 215-219 (1982; Zbl 0471.68042)]), an asymptotically optimal encoding using \(n\lceil \log_ 2n\rceil +12n\) bits is given for the labeled case.