Short encodings of planar graphs and maps (Q1805444)

The authors give space-efficient binary encoding and decoding algorithms for several classes of unlabelled planar graphs and maps, which run in linear time and provide the most compact encoding. They construct a particular depth-first search tree of a map and sequentially delete the non-tree edges and add one-bit labels. This converts the map into a labelled version of the search tree. The tree is encoded in any standard way. In this way, they obtain: A loop- and stick-free map with \(m\) edges can be encoded in \(3m+ O(1)\) bits. An arbitrary planar graph with \(m\) edges can be encoded in \(m\text{ lg } 12+ O(1)\) bits.