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

40 Scopus citations

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.

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

Keywords

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

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint

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

Cite this