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
SN - 1536-383X
VL - 26
SP - 607
EP - 630
JO - Fullerenes Nanotubes and Carbon Nanostructures
JF - Fullerenes Nanotubes and Carbon Nanostructures
IS - 10
ER -