Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings
<|reference_start|>Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings: 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.<|reference_end|>
@article{he2001linear-time,
    title={Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings},
    author={Xin He, Ming-Yang Kao, Hsueh-I Lu},
    journal={SIAM Journal on Discrete Mathematics, 12(3):317--325, 1999},
    year={2001},
    archivePrefix={arXiv},
    eprint={cs/0101033},
    primaryClass={cs.DS cs.GR}
}