  Let G be a plane graph of n nodes, m edges, f faces, and no self-loop. G need
not be connected or simple (i.e., free of multiple edges). We give three sets
of coding schemes for G which all take O(m+n) time for encoding and decoding.
Our schemes employ new properties of canonical orderings for planar graphs and
new techniques of processing strings of multiple types of parentheses.
  For applications that need to determine in O(1) time the adjacency of two
nodes and the degree of a node, we use 2m+(5+1/k)n + o(m+n) bits for any
constant k > 0 while the best previous bound by Munro and Raman is 2m+8n +
o(m+n). If G is triconnected or triangulated, our bit count decreases to 2m+3n
+ o(m+n) or 2m+2n + o(m+n), respectively. If G is simple, our bit count is
(5/3)m+(5+1/k)n + o(n) for any constant k > 0. Thus, if a simple G is also
triconnected or triangulated, then 2m+2n + o(n) or 2m+n + o(n) bits suffice,
respectively.
  If only adjacency queries are supported, the bit counts for a general G and a
simple G become 2m+(14/3)n + o(m+n) and (4/3)m+5n + o(n), respectively.
  If we only need to reconstruct G from its code, a simple and triconnected G
uses roughly 2.38m + O(1) bits while the best previous bound by He, Kao, and Lu
is 2.84m.
