Naming polyhedra by general face-spirals: theory and applications to fullerenes and other polyhedral molecules

Research output: Contribution to journalJournal articlepeer-review

We present a general face-spiral algorithm for cubic polyhedral graphs (including fullerenes and fulleroids), and extend it to the full class of all polyhedral graphs by way of the leapfrog transform. This yields compact canonical representations of polyhedra with a simple and intuitive geometrical interpretation, well suited for use by both computers and humans. Based on the algorithm, we suggest a unique, unambiguous, and simple notation for canonical naming of polyhedral graphs, up to automorphism, from which the graph is easily reconstructed. From this, we propose a practical nomenclature for all polyhedral molecules, and an especially compact form for the special class of fullerenes. A unique numbering of vertices is obtained as a byproduct of the spiral algorithm. This is required to denote modifications of the parent cage in IUPAC naming schemes. Similarly, the symmetry group of the molecule can be found together with the canonical general spiral at negligible cost. The algorithm is fully compatible with the classical spiral algorithm developed by Manolopoulos for fullerenes, i. e., classical spirals are accepted as input, and spiralable graphs lead to identical output. We prove that the algorithm is correct and complete. The worst case runtime complexity is for general N-vertex polyhedral graphs, with J the sum of all jump lengths. When the number of faces of any particular size is bounded by a constant, such as the case for fullerenes, this reduces to . We have calculated canonical general spirals for all 1,943,623,681 fullerene isomers from C20 to C200, as well as for all fullerene graphs that require jumps up to C400. Further, we have calculated canonical general spirals for large fullerenes with few or no classical spirals: the non-spiralable chiral T-C380, D3-C384, D3-C440, and D3-C672 fullerenes, and all their Goldberg Coxeter transforms up to C50, 000, and GC transforms of assorted fullerenes with no pentagon spiral starts. We verify exhaustively that the algorithm is linear for all the 2.7 × 10^12 fullerene isomers up to C400, and show that this holds also for 11,413 large GC-transform fullerenes up to C50, 000. On the used hardware, each single general spiral took about N × 200ns to produce for a CN fullerene, and the canonical general spiral was found in N × 22μs–32μs. Hence, we claim the algorithm to be efficient even for very large polyhedra. The algorithm is implemented in our program package Fullerene. In addition, the source code for a reference implementation of our proposed nomenclature for polyhedral molecules can be downloaded from http://erda.ku.dk/vgrid/Polyhedra/spirals/.
Original languageEnglish
JournalFullerenes Nanotubes and Carbon Nanostructures
Volume26
Issue number10
Pages (from-to)607-630
Number of pages24
ISSN1536-383X
DOIs
Publication statusPublished - 3 Oct 2018

    Research areas

  • Polyhedra, fullerenes, general face-spirals, polydedral molecules

Number of downloads are based on statistics from Google Scholar and www.ku.dk


No data available

ID: 186935586