Linear-time succinct encodings of planar graphs via canonical orderings

Xin He*, Ming Yang Kao, Hsueh I. Lu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

30 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)317-325
Number of pages9
JournalSIAM Journal on Discrete Mathematics
Issue number3
StatePublished - Sep 1999


  • Canonical ordering
  • Data compression
  • Graph encoding
  • Planar graphs
  • Triangulations
  • Triconnected graphs

ASJC Scopus subject areas

  • Mathematics(all)


Dive into the research topics of 'Linear-time succinct encodings of planar graphs via canonical orderings'. Together they form a unique fingerprint.

Cite this