A Simple Canonical Code for Fullerene Graphs

Naoki SHIMOTSUMA  Shin-ichi NAKANO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E92-A   No.12   pp.3398-3400
Publication Date: 2009/12/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E92.A.3398
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: Algorithms and Data Structures
Keyword: 
graph,  algorithm,  

Full Text: PDF(245.8KB)>>
Buy this Article




Summary: 
In this paper we give a simple algorithm to compute a canonical code for fullerene graphs. Our algorithm runs in O(n) time, while the best known algorithm runs in O(n2) time. Our algorithm is simple. One can generalize the algorithm to compute a canonical code for the skeleton of a convex polyhedron with n vertices. The algorithm runs in O(n2) time.