Compact encodings of planar graphs via canonical ordering and multiple parentheses

Abstract. We consider the problem of coding planar graphs by binary strings. Depending on whether O(1)-time queries for adjacency and de-gree are supported, we present hree 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. 1 In t roduct ion This paper investigates the problem of encoding a graph G with n nodes and m edges into a binary string S. This problem has been extensively studied with three objectives: (1) minimizing the length of S, (2) minimizing the time needed to compute and decode S, and (3) supporting queries efficiently. A number of coding schemes with different rade-offs have been proposed. The adjacency-list encoding of a graph is widely useful but requires 2m[logn] bits. (All logarithms are of base 2.) A folklore scheme uses 2n bits to encode a rooted n-node tree into a string of n pairs of balanced parentheses. Since the total number of such trees is at least ~. (n-1)!(n-1)! ' the minimum numbe