This task will explore new ways of understanding (sp$^2$-like) cubic-graph carbon surfaces (fullerenes, fulleroids, and Schwarzites) through local unfoldings to the Eisenstein ring and the special brand of discrete geometry that I have developed over the past two years. The theory and methods are based on graph theory and polyhedral metrics, and works from local manifold information without a global coordinate system.

Preliminary Work

The most important subtasks of Task M are

1. Algorithms to derive polyhedral Riemann-metric from graph.
2. Unfolding to — and re-folding from — Eisenstein polygons: "molecular origami"-algorithms.
3. Canonical representations through generalized spirals.
4. Algebraic properties and transformations in the Eisenstein ring.
5. Symmetry-reduction; generating subsets; symmetric unfoldings with geometric constraints.

The mathematical theory, algorithm for Subtask 1 was presented in "Solving Wave Equations on Discrete non-Euclidean Surfaces", 2017, and a paper is in progress, titled Exact shortest geodesics on deltahedra manifolds. A brief summary of the work is given below.

Similarly, a paper is under preparation for Subtask 2, titled Unfolding and folding deltahedra on the Eisenstein ring, also outlined below.

For Subtask 4, I have implemented automorphism group computation for arbitrary polyhedral graphs, and spatial point group computation for fullerenes, by the method I describe in Wirz, Schwerdtfeger, and Avery 2017, Naming Polyhedra by General Face-Spirals , as well as a prototype of maximally symmetric planar drawings and unfoldings. Progress of the algorithms and software prototypes will be described below.

The fast computation of the canonical general spiral for a cubic polyhedral graph, which we have described in our 2017 paper Naming Polyhedra by General Face-Spirals, at the same time computes a compact representation of the graph's automorphism group. This work is implemented in the development version of our Fullerene software. It is also included in the files libgraph/symmetry.hh and libgraph/symmetry.cc in our small reference implementation of our general spiral representations of general polyhedra, which can be found here:

It works as follows: Assume that we are given the fullerene graph dual $G^*$, constructed from a general spiral $S = (d_1,d_2,\ldots,d_{N_f})$, and wish to compute the automorphism group of $G^*$. Since $G^*$ is constructed from $S$, the entries in $S$ correspond to the degrees of vertex number $1,2,\ldots,N_f$ in $G^*$. For every vertex $v$ of degree $d_1$, we have $2 d_1$ different spiral starts: $d_1$ for clockwise and $d_1$ for counter-clockwise traversal. If a spiral start $(f_1,f_2,f_3)$ unwinds $G^*$ to the input spiral $S$, there is an automorphism of $G^*$ that maps $(1,2,3) \mapsto (f_1,f_2,f_3)$. These are all the automorphisms, and the number of starts that unwind to $S$ is the order of the automorphism group (see The topology of fullerenes, pages 109 through 111, for details). For fullerenes, we can use the pentagon index representations of the general spirals to obtain a representation of the automorphism group from only $\approx 12$ integers per group generator, i.e., small near-constant size, and similarly for more general fulleroids by using the representation of non-hexagon indices in the spiral.

This information can be obtained while computing the canonical general spiral: The face sequence corresponding to each spiral unwinding is temporarily stored together with the spiral, and the ones corresponding to the canonical spiral (the lexicographically smallest one) define the group elements by the following permutation representation: $$ \pi_F(g) = \left( \begin{smallmatrix} 1 & 2 & 3 & \cdots & N_f\\ f_1 & f_2 & f_3 & \cdots & f_{N_f} \end{smallmatrix} \right) $$ This is a faithful representation of the group, and if we wish, we can easily build the multiplication table by composing all pairs of the permutations, or calculate characters, irreducible representations, and all other properties; and we can identify the group.

For the method defined by the \Mano{} spirals, it was necessary to compute spirals for all $6N$ spiral starts in order to compute the symmetry group, since many graphs have no regular spiral starting in a non-hexagon face and would otherwise fail. Since the general spirals always succeed, this is no longer necessary. For fullerenes and other polyhedra with bounded number of negative curvature faces, this reduces the complexity by an order, yielding the symmetry group in linear time (and obtained for free when computing the canonical general spiral), and a near-constant size representation of the group. And, more importantly, it always works.

Because the leapfrog transform preserves symmetry, this yields a rapid method for computing the symmetry group for any polyhedral graph, not just for cubic ones.

We note that there are several algorithms already available to obtain the group automorphism of a general graph (Junttila and Kaski 2007,Darga et al. 2008,McKay and Piperno 2014). However, these are significantly more difficult to understand and implement than the general spirals, and all yield representations of size $\mathcal{O}(N)$ or larger, even in cases such as fullerenes, where our general spiral scheme usually produces group representations of size $\mathcal{O}(1)$. An advantage is that we can get everything at once: A canonical graph representation, easy to understand nomenclature, canonical vertex numbering, and the symmetry group.

In addition to the abstract symmetry group (fully defined by the multiplication table of the automorphisms), we are often interested in the symmetry 3D {\em point group}. Such a (molecular) point group has not just the group multiplication rules, but is the largest set of {\em isometries} that leave the polyhedron invariant. The point group has additional structure compared to the abstract symmetry group of graph automorphisms. For example, the point groups $D_2$, $S_4$, $C_{2h}$, and $C_{2v}$ all have the same group structure, namely the Klein 4-group $\mathbb{Z}_2 \times \mathbb{Z}_2$; but they represent different geometrical symmetries.

The point group corresponds to the rotations, reflections, roto-inversions, and inversions that leave the ideal polyhedron invariant. A strong theorem by Mani (Mani 1971, Automorphismen von polyedrischen Graphen ) states that any 3-connected cubic graph can be embedded in space as a convex polyhedron, the unique point group of which realizes the full automorphism group of the graph. That is: every graph automorphism of a cubic polyhedral graph is also a rotation or reflection of its ideal polyhedral shape.

In The topology of fullerenes, 2014, we detail a scheme for computing the point groups for fullerenes by way of orbits on faces, edges, and vertices, and a decision tree.\footnote{The scheme is discussed already in Fowler's An Atlas of Fullerenes, 2006, but we have not found a complete description in the literature outside of our own in The topology of fullerenes. This is specific for the 28 fullerene point groups, but similar schemes can be derived by hand for larger classes of polyhedra that have a finite set of point groups. A complete and fully automatic method for identifying the 3D point groups of general polyhedral graphs is to our knowledge still an open problem.

My code for computing the point groups of fullerenes in $\mathcal{O}(N)$ time is included both in the development version of Fullerene in the files libgraph/symmetry.cc and libgraph/symmetry.hh.

For fullerenes, the point group is calculated as follows: The symmetry points of interest in a fullerene are the vertices, midpoints of edges, the barycenter of the polygons and the whole cage, the latter having the full symmetry of the point group. They have certain site symmetries according to the rotational axes or mirror planes going through these symmetry points, which are collected in the table below. The full isometry group $\mathcal{G}$, which correspond to the rotations, reflections, roto-inversions, and inversions that leave the ideal polyhedron invariant, also act as permutations of the symmetry points, the action always being a subgroup of $\mathcal{G}$. The permutations of the symmetry points in fact completely determine the point group symmetry, and we can find the full point group of the graph $G$ (or, equivalently, its dual $G^*$) as follows: In step 1, one computes the face permutation representation $\pi_F$ of the abstract group, as described above. From this one derives vertex and edge permutation representations $\pi_V$ and $\pi_E$ by acting with every group operation on the dual graph.

In step 2 one computes the vertex, edge, and face \emph{group orbits} by acting with the permutation representations on every vertex, edge, and face. Each orbit belongs to a certain site-symmetry group as shown in Table~\ref{SiteSymmetry}. The site-symmetry groups are determined by the orbit sizes. For example, the site-symmetry group of the face $f_i$ has order $|\mathcal{G}_{f_i}| = |\mathcal{G}|/|\mathcal{G} f_i|$. By counting the number of sites belonging to each site-symmetry group, we obtain a signature that uniquely identifies the point group. $$ m_F(k) = \left|\left\{f\in F \| k = \frac{|\mathcal{G}|}{|\mathcal{G} f|}\right\}\right|, \ \ m_E(k) = \left|\left\{e\in E \| k = \frac{|\mathcal{G}|}{|\mathcal{G} e|}\right\}\right|, \ \ \text{ and } \ \ m_V(k) = \left|\left\{v\in V \| k = \frac{|\mathcal{G}|}{|\mathcal{G} v|}\right\}\right| $$

The information can be condensed to a \emph{site-symmetry count} for each site-group order: \begin{equation} m_S(k) = m_F(k) + m_E(k) + m_V(k) \end{equation} In the final step, the point group is determined by the site-symmetry counts by the decision tree structure shown in Figure~\ref{fig:symmetry-tree}. The method can be extended to any fullerene and fulleroid by using general spirals. However, for every possible point group, the site-symmetry signature must be worked out and added to the decision tree.

Once the point group has been determined, the number of infra-red and Raman active lines, as well as the $^{13}$C NMR pattern can be derived. Moreover, point groups lacking an inversion center are further divided into polar and chiral point groups. A {\it chiral point group} is one without any roto-inversion symmetry elements, and a {\it polar point group} allows for the fullerene to have a dipole moment. A point group with an inversion center or a mirror plane perpendicular to the axis of rotation cannot be polar. The nine chiral point groups for fullerenes are $I, T, D_6, D_5, D_3, D_2, C_3, C_2$, and $C_1$. The polar fullerenes belong to either of the point groups $C_{3v}, C_3, C_{2v}, C_2, C_s$ or $C_1$. For larger fullerenes, the fraction of low-symmetry to high-symmetry isomers grows rapidly, and the $C_1$ point group increasingly dominates. This can be intuitively understood combinatorially from distributing pentagons on a sphere. Already at C100, more than 99% of the isomers are $C_1$.

The separation of spiral starts into equivalence classes by their spirals yields an interesting relation: \begin{equation} |\mathcal{G}| = \frac{6N}{N_{\text{spirals}}^s} \end{equation} where $N_{\text{spirals}}^s$ is the number of symmetry distinct (general) spirals. For $I_h$ symmetry we have $|I_h|=120$, which gives $N=20 N_{\text{spirals}}^s$. Hence, $I_h$-fullerenes can only occur when $N$ is a multiple of 20. In a similar way, for $I$ symmetry we have $N=10 N_{\text{spirals}}^s$, and for $T_d, T_h, D_{6h}$, or $D_{6d}$ we obtain $N=4N_{\text{spirals}}^s$. This explains why some of these high symmetry groups are not found in certain isomer lists.

In the case of icosahedral symmetry, we have a full characterization of when they occur: As proved by Dutour and Deza, every fullerene of $I_h$ or $I$ symmetry is a Goldberg-Coxeter transform of C20. This means that they occur exactly when $N=20(k^2+kl+l^2)$ for integers $k$ and $l$. It is also possible to determine when these are of $I_h$ and when they are of %chg: the characterization is complete. $I$ symmetry. Halma and leapfrog transformations, which correspond to Goldberg-Coxeter transforms of $l=0$ and $k=l$, respectively, both preserve the symmetry. Hence, there is a fullerene with $I_h$ symmetry at $N=20j^2$ and $N=20(3j^2)$ for every $j\in\mathbb N$, corresponding to a single Halma or leapfrog transformation on C20. Consecutive application of the two shows that isomers with $I_h$ symmetry are found for every $N=20(3^ij^2)$ ($j\in \mathbb{N}$ and $i=0,1$). Moreover, general Goldberg-Coxeter $(k,l)$ transforms with $k\ne l$ and $l\ne 0$ ($k > 0$) break horizontal mirror plane symmetry.

//////////////////////////////////////////////////////////////////////
//	      POINT GROUPS FOR FULLEROIDS OF DEGREE <= 6
//////////////////////////////////////////////////////////////////////
// Reference: Deza-2009, Theorem 2.1 (iii)
PointGroup PointGroup::FullereneSymmetries[28] = {
  {C,1},      {C,2},       {C,REF_I},   {C,REF_S},
  {C,3},      {D,2},       {S,4},       {C,2,REF_V},
  {C,2,REF_H},{D,3},       {S,6},       {C,3,REF_V},
  {C,3,REF_H},{D,2,REF_H}, {D,2,REF_D}, {D,5},  
  {D,6},      {D,3,REF_H}, {D,3,REF_D}, {T},  
  {D,5,REF_H},{D,5,REF_D}, {D,6,REF_H}, {D,6,REF_D}, 
  {T,REF_D},  {T,REF_H},   {I},         {I,REF_H}
};

PointGroup Symmetry::point_group() const
{
  vector 
    mF = site_symmetry_counts(G),
    mV = site_symmetry_counts(Gtri),
    mE = site_symmetry_counts(Gedge);

  vector mS(13,0);
  for(int i=0;i<12;i++) mS[i+1] = mF[i] + mV[i] + mE[i];
  
  switch(G.size()){
  case 1:
    return PointGroup("C1");

  case 2:
    switch(mS[2]){
    case 0: 
      return PointGroup("Ci");
    case 2:
      return PointGroup("C2");
    default:
      if(mS[2]>2) 
	return PointGroup("Cs");
    }
    break;
  case 3:
    return PointGroup("C3");

  case 4: 
    switch(mS[4]){
    case 0:
      switch(mS[2]){
      case 1:
	return PointGroup("S4");
      case 3: 
	return PointGroup("D2");
      default:
	if(mS[2]>3) return PointGroup("C2h");
      }
      break;
    case 2:
      return PointGroup("C2v");
    default:
      break;
    }
    break;
  case 5:  // No fullerene groups of order 5 -- fill out for fulleroids
    break;

  case 6:
    switch(mS[6]){
    case 0:
      switch(mS[2]){
      case 0:
	return PointGroup("S6");
      case 2:
	return PointGroup("D3");
      default:
	if(mS[2]>2) return PointGroup("C3h");	
      }
      break;
    case 2:
      return PointGroup("C3v");
    default:
      break;
    }
    break;

  case 7:  // No fullerene groups of order 7 -- fill out for fulleroids
    break;

  case 8:
    switch(mS[4]){
    case 1: 
      return PointGroup("D2d");
    case 3:
      return PointGroup("D2h");
    default:
      break;
    }
    break;

  case 10:
    return PointGroup("D5");

  case 12:
    switch(mS[6]){
    case 0:
      return PointGroup("T");
    case 1:
      switch(mS[4]){
      case 0:
	switch(mS[2]){
	case 2:
	  return PointGroup("D6");
	default:
	  if(mS[2]>2) return PointGroup("D3d");
	}
	break;
      case 2:
	return PointGroup("D3h");
      default:
	break;
      }     
    default:
      break;
    }
    break;

  case 20:
    switch(mS[4]){
    case 0:
      return PointGroup("D5d");
    case 2:
      return PointGroup("D5h");
    default:
      break;
    }
    break;

  case 24:
    switch(mS[12]){
    case 0:
      switch(mS[6]){
      case 0:
	return PointGroup("Th");
      case 2:
	return PointGroup("Td");
      default:
	break;
      }
      break;
    case 1:
      switch(mS[4]){
      case 0:
	return PointGroup("D6d");
      case 2:
	return PointGroup("D6h");
      default:
	break;
      }
    default:
      break;
    }
    break;
    
  case 60:
    return PointGroup("I");

  case 120:
    return PointGroup("Ih");

  default:
    break;
  }

  return PointGroup();
}