TY - JOUR

T1 - Naming polyhedra by general face-spirals

T2 - theory and applications to fullerenes and other polyhedral molecules

AU - Wirz, Lukas

AU - Schwerdtfeger, Peter

AU - Avery, James Emil

PY - 2018/10/3

Y1 - 2018/10/3

N2 - 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/.

AB - 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/.

KW - Polyhedra

KW - fullerenes

KW - general face-spirals

KW - polydedral molecules

UR - http://www.scopus.com/inward/record.url?scp=85051760150&partnerID=8YFLogxK

U2 - 10.1080/1536383X.2017.1388231

DO - 10.1080/1536383X.2017.1388231

M3 - Journal article

VL - 26

SP - 607

EP - 630

JO - Fullerenes Nanotubes and Carbon Nanostructures

JF - Fullerenes Nanotubes and Carbon Nanostructures

SN - 1536-383X

IS - 10

ER -