  Let G be an embedded planar undirected graph that has n vertices, m edges,
and f faces but has no self-loop or multiple edge. If G is triangulated, we can
encode it using {4/3}m-1 bits, improving on the best previous bound of about
1.53m bits. In case exponential time is acceptable, roughly 1.08m bits have
been known to suffice. If G is triconnected, we use at most
(2.5+2\log{3})\min\{n,f\}-7 bits, which is at most 2.835m bits and smaller than
the best previous bound of 3m bits. Both of our schemes take O(n) time for
encoding and decoding.
