Clusters of cycles (Q1602420)

An \((r,q)\)-polycycle is a simple planar 2-connected finite or countable graph \(G\) of girth \(r\) and maximal vertex-degree \(q\), which admits an \((r,q)\)-polycyclic realization \(P(G)\) on the plane. Such a realization has the following characteristics: (i) all interior vertices are of degree \(q\); (ii) all interior faces (denote their number by \(p_r\)) are combinatorial \(r\)-gons; (iii) all vertices, edges and interior faces form a cell-complex. An example of an \((r,q)\)-polycycle is the skeleton of \((r^q)\), i.e., of the \(q\)-valent partition of the sphere, Euclidean plane or hyperbolic plane by regular \(r\)-gons. This paper gives a compact survey of results on \((r,q)\)-polycycles. Call a polycycle proper if it is a partial subgraph of \((r^q)\) and helicene, otherwise. The authors listed the \((4,3)\)-, \((3,4)\)-helicenes and the number of \((5,3)\)-, \((3,5)\)-helicenes for first interesting \(p_r\). They also obtained results about outerplanar polycycles. Call a polycycle \(G\) isotoxal (IT), isogonal (IG), or isohedral (IH) if its symmetric group \(\text{Aut}(G)\) is transitive on edges, vertices, or interior faces, respectively. The authors listed all IG- or IH-polycycles for spheric \((r,q)\) and constructed many examples of IH-polycycles for the general case. They also determined some interesting properties of these classes of polycycles. The authors found for the spheric \((r,q)\) the maximal number \(n_{\text{int}}\) of interior points for an \((r,q)\)-polycycle with given \(p_r\). They also found all non-extendible \((r,q)\)-polycycles. Finally the authors discussed problems concerning isometric embeddings of polycycles into hypercubes, half-hypercubes and cubic lattices and its half when the polycycles are infinite.