Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Compact encodings of planar graphs via canonical orderings and multiple parentheses
| |
|
Compact encodings of planar graphs via canonical orderings and multiple parentheses
Richie Chih-Nan Chuang1  , Ashim Garg2 , Xin He2 , Ming-Yang Kao3 and Hsueh-I Lu1
| (1) |
Department of Computer Science and Information Engineering, National Chung-Cheng University, 621 Chia-Yi, Taiwan |
| (2) |
Department of Computer Science, State University of New York at Buffalo, 14260 Buffalo, NY, USA |
| (3) |
Department of Computer Science, Yale University, 06250 New Haven, CT, USA |
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.
Research supported in part by NSF Grant CCR-9205982.
Research supported in part by NSF Grant CCR-9531028.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|