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

• Published in: Fullerenes, nanotubes, and carbon nanostructures nanotubes, and carbon nanostructures, 2018-10, Vol.26 (10), p.607-630
• Main Authors: Wirz, Lukas N., Schwerdtfeger, Peter, Avery, James E.
• Format: Article
• Language: English
• Subjects: fullerenes; general face-spirals; polydedral molecules; Polyhedra
• ISSN: 1536-383X; 1536-4046
• DOI: 10.1080/1536383X.2017.1388231

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 2,157,751,423 fullerene isomers from C 20 to C 200 , as well as for all fullerene graphs that require jumps up to C 400 . Further, we have calculated canonical general spirals for large fullerenes with few or no classical spirals: all the Goldberg-Coxeter transforms up to C 50,000 of the the non-spiralable chiral T-C 380 , D 3 -C 384 , D 3 -C 440 , and D 3 -C 672 fullerenes, and for 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 C 400 , and show that this holds also for 11,413 large GC-transform fullerenes up to C 50,000 . On the used hardware, each single general spiral took about N × 200ns to produce for a C N 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