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

56 Citations (Scopus)

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

Planar graph
Decoding
Encoding
Coding
Adjacency
Linear Time
Strings
Query
Binary

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).
Chuang, Richie Chih Nan ; Garg, Ashim ; He, Xin ; Kao, Ming Yang ; Lu, Hsueh I. / Compact encodings of planar graphs via canonical orderings and multiple parentheses. Automata, Languages and Programming - 25th International Colloquium, ICALP 1998, Proceedings. 1998. pp. 118-129 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{b36f83cc0cd146628271820ff2a87257,
title = "Compact encodings of planar graphs via canonical orderings and multiple parentheses",
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.",
author = "Chuang, {Richie Chih Nan} and Ashim Garg and Xin He and Kao, {Ming Yang} and Lu, {Hsueh I.}",
year = "1998",
month = "12",
day = "1",
language = "English (US)",
isbn = "3540647813",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "118--129",
booktitle = "Automata, Languages and Programming - 25th International Colloquium, ICALP 1998, Proceedings",

}

Chuang, RCN, Garg, A, He, X, Kao, MY & Lu, HI 1998, Compact encodings of planar graphs via canonical orderings and multiple parentheses. in Automata, Languages and Programming - 25th International Colloquium, ICALP 1998, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1443 LNCS, pp. 118-129, 25th International Colloquium on Automata, Languages and Programming, ICALP 1998, Aalborg, Denmark, 7/13/98.

Compact encodings of planar graphs via canonical orderings and multiple parentheses. / Chuang, Richie Chih Nan; Garg, Ashim; He, Xin; Kao, Ming Yang; Lu, Hsueh I.

Automata, Languages and Programming - 25th International Colloquium, ICALP 1998, Proceedings. 1998. p. 118-129 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1443 LNCS).

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

TY - GEN

T1 - Compact encodings of planar graphs via canonical orderings and multiple parentheses

AU - Chuang, Richie Chih Nan

AU - Garg, Ashim

AU - He, Xin

AU - Kao, Ming Yang

AU - Lu, Hsueh I.

PY - 1998/12/1

Y1 - 1998/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84878620879&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84878620879&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84878620879

SN - 3540647813

SN - 9783540647812

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 118

EP - 129

BT - Automata, Languages and Programming - 25th International Colloquium, ICALP 1998, Proceedings

ER -

Chuang RCN, Garg A, He X, Kao MY, Lu HI. Compact encodings of planar graphs via canonical orderings and multiple parentheses. In Automata, Languages and Programming - 25th International Colloquium, ICALP 1998, Proceedings. 1998. p. 118-129. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).