Linear-time succinct encodings of planar graphs via canonical orderings
Journal
SIAM Journal on Discrete Mathematics
Journal Volume
12
Journal Issue
3
Pages
317-325
Date Issued
1999
Author(s)
He, X.
Kao, M.-Y.
HSUEH-I LU
Abstract
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/3m - 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.
Type
journal article