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

doi:10.1007/bfb0055046

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

Department of Computer Science and Engineering

National Chung Cheng University
SUNY Buffalo
Yale University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

74 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 language	English
Title of host publication	Automata, Languages and Programming - 25th International Colloquium, ICALP 1998, Proceedings
Publisher	Springer Verlag
Pages	118-129
Number of pages	12
ISBN (Print)	3540647813, 9783540647812
DOIs	https://doi.org/10.1007/bfb0055046
State	Published - 1998
Event	25th International Colloquium on Automata, Languages and Programming, ICALP 1998 - Aalborg, Denmark Duration: Jul 13 1998 → Jul 17 1998

Publication series

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

Conference

Conference	25th International Colloquium on Automata, Languages and Programming, ICALP 1998
Country/Territory	Denmark
City	Aalborg
Period	07/13/98 → 07/17/98

Access to Document

10.1007/bfb0055046

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). Springer Verlag. https://doi.org/10.1007/bfb0055046

Chuang, Richie Chih Nan ; Garg, Ashim ; He, Xin et al. / Compact encodings of planar graphs via canonical orderings and multiple parentheses. Automata, Languages and Programming - 25th International Colloquium, ICALP 1998, Proceedings. Springer Verlag, 1998. pp. 118-129 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a10daef016354e8f916ab98f916b31a5,

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",

doi = "10.1007/bfb0055046",

language = "English",

isbn = "3540647813",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "118--129",

booktitle = "Automata, Languages and Programming - 25th International Colloquium, ICALP 1998, Proceedings",

address = "Germany",

note = "25th International Colloquium on Automata, Languages and Programming, ICALP 1998 ; Conference date: 13-07-1998 Through 17-07-1998",

}

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, Springer Verlag, pp. 118-129, 25th International Colloquium on Automata, Languages and Programming, ICALP 1998, Aalborg, Denmark, 07/13/98. https://doi.org/10.1007/bfb0055046

Compact encodings of planar graphs via canonical orderings and multiple parentheses. / Chuang, Richie Chih Nan; Garg, Ashim; He, Xin et al.
Automata, Languages and Programming - 25th International Colloquium, ICALP 1998, Proceedings. Springer Verlag, 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 proceeding › Conference contribution › peer-review

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

Y1 - 1998

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 - https://www.scopus.com/pages/publications/84878620879

U2 - 10.1007/bfb0055046

DO - 10.1007/bfb0055046

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

PB - Springer Verlag

T2 - 25th International Colloquium on Automata, Languages and Programming, ICALP 1998

Y2 - 13 July 1998 through 17 July 1998

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. Springer Verlag. 1998. p. 118-129. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/bfb0055046

Compact encodings of planar graphs via canonical orderings and multiple parentheses

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this