Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses

摘要

We consider the problem of coding planar graphs by binary strings. Depending on whether O(l)-time queries for adjacency and degree are supported, we present three sets of coding schemes which all take linear time for encoding and decoding. The encoding lengths are significantly shorter than the previously known results in each case.