Compact encodings of planar graphs via canonical orderings and multiple parentheses

Richie Chih Nan Chuang, Ashim Garg, Xin He, Ming Yang Kao, Hsueh I. Lu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

57 Scopus citations

Abstract

We consider the problem of coding planar graphs by binary strings. Depending on whether O(1)-time queries for adjacency and degree are supported, we present three sets of coding schemes which all take linear time for encoding and decoding. The encoding lengths are significantly shorter than the previously known results in each case.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 25th International Colloquium, ICALP 1998, Proceedings
Pages118-129
Number of pages12
StatePublished - Dec 1 1998
Event25th International Colloquium on Automata, Languages and Programming, ICALP 1998 - Aalborg, Denmark
Duration: Jul 13 1998Jul 17 1998

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1443 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other25th International Colloquium on Automata, Languages and Programming, ICALP 1998
CountryDenmark
CityAalborg
Period7/13/987/17/98

    Fingerprint

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Chuang, R. C. N., Garg, A., He, X., Kao, M. Y., & Lu, H. I. (1998). Compact encodings of planar graphs via canonical orderings and multiple parentheses. In Automata, Languages and Programming - 25th International Colloquium, ICALP 1998, Proceedings (pp. 118-129). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1443 LNCS).