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

66 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
PublisherSpringer Verlag
Pages118-129
Number of pages12
ISBN (Print)3540647813, 9783540647812
DOIs
StatePublished - 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
Country/TerritoryDenmark
CityAalborg
Period7/13/987/17/98

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Compact encodings of planar graphs via canonical orderings and multiple parentheses'. Together they form a unique fingerprint.

Cite this