Goldberg–Coxeter construction

The Goldberg–Coxeter construction or Goldberg–Coxeter operation (GC construction or GC operation) is a graph operation defined on regular polyhedral graphs with degree 3 or 4. It also applies to the dual graph of these graphs, i.e. graphs with triangular or quadrilateral "faces". The GC construction can be thought of as subdividing the faces of a polyhedron with a lattice of triangular, square, or hexagonal polygons, possibly skewed with regards to the original face: it is an extension of concep…

Page content (https://en.wikipedia.org/w/index.php?title=Goldberg–Coxeter_construction&oldid=1048157967)

Jump to content Main menu Main menu move to sidebar hide Navigation Main page Contents Current events Random article About Wikipedia Contact us Contribute Help Learn to edit Community portal Recent changes Upload file Special pages Search Search Appearance Donate Create account Log in Personal tools Donate Create account Log in Contents move to sidebar hide (Top) 1 History 2 Construction Toggle Construction subsection 2.1 Master polygons 2.1.1 Master polygons for triangles 2.1.2 Master polygons for squares 2.2 Performing the GC construction 3 Extensions 4 See also 5 Footnotes 6 References Toggle the table of contents Goldberg–Coxeter construction Add languages Add links Article Talk English Read Edit View history Tools Tools move to sidebar hide Actions Read Edit View history General What links here Related changes Upload file Permanent link Page information Cite this page Get shortened URL Print/export Download as PDF Printable version In other projects Wikidata item Appearance move to sidebar hide From Wikipedia, the free encyclopedia This is an old revision of this page, as edited by 2601:445:4380:7dd0::533e ( talk ) at 15:40, 4 October 2021 (punctuation) . The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision . Revision as of 15:40, 4 October 2021 by 2601:445:4380:7dd0::533e ( talk ) (punctuation) ( diff ) ← Previous revision | Latest revision ( diff ) | Newer revision → ( diff ) Goldberg polyhedron (3,1) and geodesic polyhedron (3,1). The Goldberg polyhedra and geodesic polyhedra were precursors to the Goldberg–Coxeter operation. The Goldberg–Coxeter construction or Goldberg–Coxeter operation ( GC construction or GC operation ) is a graph operation defined on regular polyhedral graphs with degree 3 or 4. 1 2 It also applies to the dual graph of these graphs, i.e. graphs with triangular or quadrilateral "faces". The GC construction can be thought of as subdividing the faces of a polyhedron with a lattice of triangular, square, or hexagonal polygons, possibly skewed with regards to the original face: it is an extension of concepts introduced by the Goldberg polyhedra and geodesic polyhedra . The GC construction is primarily studied in organic chemistry for its application to fullerenes , 1 2 but it has been applied to nanoparticles , 3 computer-aided design , 4 basket weaving , 5 6 and the general study of graph theory and polyhedra . 7 The Goldberg–Coxeter construction may be denoted as G C k , ℓ ( G 0 ) {\displaystyle GC_(G_)} , where G 0 {\displaystyle G_} is the graph being operated on, k {\displaystyle k} and l {\displaystyle l} are integers, k > 0 {\displaystyle k>0} , and ℓ ≥ 0 {\displaystyle \ell \geq 0} . History Michael Goldberg introduced the Goldberg polyhedron in 1937. 8 Buckminster Fuller coined the term " geodesic dome " in the 1940s, although he largely kept the mathematics behind the domes a trade secret. 9 Geodesic domes are the geometric dual of (a section of) a Goldberg polyhedron: a full geodesic dome can be thought of as a geodesic polyhedron , dual to the Goldberg polyhedron. In 1962, Donald Caspar and Aaron Klug published an article on the geometry of viral capsids that applied and expanded upon concepts from Goldberg and Fuller. 10 H.S.M. Coxeter published an article in 1971 covering much of the same information. 11 Caspar and Klug were the first to publish the most general correct construction of a geodesic polyhedron, making the name "Goldberg–Coxeter construction" an instance of Stigler's law of eponymy . 12 The discovery of Buckminsterfullerene in 1985 motivated research into other molecules with the structure of a Goldberg polyhedron. The terms "Goldberg–Coxeter fullerene" and "Goldberg–Coxeter construction" were introduced by Michel Deza in 2000. 13 14 This is also the first time the degree 4 case was considered. Construction This section largely follows Deza et al.'s two articles. 1 2 Master polygons Lattices n-Regular 3 4 Domain Eisenstein a + b u {\displaystyle a+bu} Gaussian a + b i {\displaystyle a+bi} Adjoined unit u = 1 2 ( 1 + i 3 ) = e 1 3 π i = ω + 1 {\displaystyle {\beginu&=}\left(1+i}\right)\&=e^{{\frac {1}}\pi i}=\omega +1\end}} i = − 1 {\displaystyle i=}} Norm t ( a , b ) {\displaystyle t(a,b)} a 2 + a b + b 2 {\displaystyle a^{2}+ab+b} a 2 + b 2 {\displaystyle a^{2}+b} . Master polygon ( 0 , x , x u ) {\displaystyle (0,x,xu)} ( 0 , x , x ( 1 + i ) , x i ) {\displaystyle (0,x,x(1+i),xi)} Regular lattices over the complex plane can be used to create "master polygons". In geodesic dome terminology, this is the "breakdown structure" or "principal polyhedral triangle" (PPT). The 4-regular case uses the square lattice over the Gaussian integers , and the 3-regular case uses triangular lattice over the Eisenstein integers . For convenience, an alternate parameterization of the Eisenstein integers is used, based on the sixth root of unity instead of the third. a The usual definition of Eisenstein integers uses the element ω = 1 2 ( − 1 + i 3 ) = e 2 3 π i = u − 1 {\textstyle \omega =}\left(-1+i}\right)=e^{{\frac {2}}\pi i}=u-1} . A norm, t ( k , ℓ ) {\displaystyle t(k,\ell )} , is defined as the square of the absolute value of the complex number. For 3-regular graphs this norm is the T-number or triangulation number used in virology. The master polygon is an equilateral triangle or square laid over the lattice. The table to the right gives formulas for the vertices of the master polygons in the complex plane, and the gallery below shows the (3,2) master triangle and square. So that the polygon can be described by a single complex number, one vertex is fixed at 0. There are multiple numbers that can describe the same polygon: these are associates of each other: if x {\displaystyle x} and y {\displaystyle y} are associates, then x = u n y {\displaystyle x=u^y} in the Eisensteins or x = i n y {\displaystyle x=i^y} in the Gaussians for some integer n {\displaystyle n} . The set of elements that are associates of each other is an equivalence class , and the element of each equivalence class that has a > 0 {\displaystyle a>0} and b ≥ 0 {\displaystyle b\geq 0} is the normal form . (3,2) master triangle over triangular grid (3,2) master square over square grid Master polygons, and the operator G C k , ℓ ( G 0 ) {\displaystyle GC_\left(G_\right)} , can be classified as follows: Class I: ℓ = 0. {\displaystyle \ell =0.} Class II: k = ℓ . {\displaystyle k=\ell .} Class III: all other. Class III operators exist in chiral pairs: G C k , ℓ ( G 0 ) {\displaystyle GC_\left(G_\right)} is the chiral pair of G C ℓ , k ( G 0 ) {\displaystyle GC_(G_)} . Below are tables of master triangles and squares. Class I corresponds to the first column, and Class II corresponds to the diagonal with a slightly darker background. Master polygons for triangles Master triangles through (8,8) 0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 Master polygons for squares Master squares through (8,8) 0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 Composition of Goldberg–Coxeter operations corresponds to multiplication of complex numbers. If and only if G C a , b ( G C c , d ( G 0 ) ) = G C e , f ( G 0 ) {\displaystyle GC_\left(GC_\left(G_\right)\right)=GC_\left(G_\right)} (i.e. the series of operations on the left produces a graph isomorphic to the one on the right), then for a 3-regular graph ( a + b u ) ( c + d u ) {\displaystyle (a+bu)(c+du)} is in the equivalence class of ( e + f u ) {\displaystyle (e+fu)} , and for a 4-regular graph ( a + b i ) ( c + d i ) {\displaystyle (a+bi)(c+di)} is in the equivalence class of ( e + f i ) {\displaystyle (e+fi)} . There are some useful consequences of this: The application of repeated Goldberg–Coxeter operations is commutative and associative . Complex conjugation of the element a + b i {\displaystyle a+bi} or a + b u {\displaystyle a+bu} corresponds to reflection of the constructed graph. Since the Gaussian integers and Euclidean integers are both Euclidean domains , elements of those domains can be uniquely factored into prime elements. Therefore, it also makes sense to decompose a Goldberg–Coxeter operator into a sequence of "prime" Goldberg–Coxeter operators, and this sequence is unique (up to rearrangement). Performing the GC construction The steps of performing the GC construction G C k , ℓ ( G 0 ) {\displaystyle GC_(G_)} are as follows: Determine the master polygon, based on k {\displaystyle k} , ℓ {\displaystyle \ell } , and G 0 {\displaystyle G_} If operating on a 3- or 4-regular graph (instead of a graph with triangular/quadrilateral faces), take its dual graph . This dual graph will have triangular or quadrilateral faces. Replace the faces of the triangulated/quadrangulated graph with the master polygon. Be aware that planar graphs have an "external" face that must be replaced as well. In the below example, this is done by attaching it to one side of the graph and connecting other sides as necessary. This temporarily introduces overlapping edges into the graph, but the resulting graph is planar. The vertices can be rearranged so that there are no overlapping edges. If the original graph was a 3- or 4-regular graph, take the dual of the result of step 3. Otherwise, the result of step 3 is the GC construction. Below is an example, where G C 1 , 1 ( G 0 ) {\displaystyle GC_(G_)} is constructed on the skeleton of a cube . In the last two graphs, blue lines are edges of G 0 {\displaystyle G_} , while black lines are edges of G C 1 , 1 ( G 0 ) {\displaystyle GC_(G_)} . (Dotted lines are normal graph edges, just drawn differently to make overlapping graph edges more visible.) Red vertices are in G 0 {\displaystyle G_} and remain in G C 1 , 1 ( G 0 ) {\displaystyle GC_(G_)} , while blue vertices are newly created by the construction and are only in G C 1 , 1 ( G 0 ) {\displaystyle GC_(G_)} . Master square (1,1) Starting polyhedron (Cube) G 0 {\displaystyle G_} , the skeleton of the cube Intermediate step of constructing G C 1 , 1 ( G 0 ) {\displaystyle GC_(G_)} . The result G C 1 , 1 ( G 0 ) {\displaystyle GC_(G_)} , after rearrangement Embedding of the result ( rhombic dodecahedron ) Extensions The Goldberg–Coxeter construction can be easily extended to some non-planar graphs, such as toroidal graphs . 15 Class III operators, because of their chirality, require a graph that can be embedded on an orientable surface , but class I and II operators can be used on non-orientable graphs. See also Wikimedia Commons has media related to Goldberg–Coxeter construction . Geodesic grid Quadrilateralized spherical cube Loop subdivision surface Catmull–Clark subdivision surface Conway polyhedron notation Footnotes ^ This simplifies the definition of the equivalence class, makes the class definition the same for 3- and 4-regular graphs, and corresponds with the parameterization traditionally used for geodesic domes and Goldberg polyhedra. References ^ a b c Deza, M.; Dutour, M (2004). "Goldberg–Coxeter constructions for 3-and 4-valent plane graphs" . The Electronic Journal of Combinatorics . 11 : #R20. doi : 10.37236/1773 . ^ a b c Deza, M.-M.; Sikirić, M. D.; Shtogrin, M. I. (2015). "Goldberg–Coxeter Construction and Parameterization" . Geometric Structure of Chemistry-Relevant Graphs: Zigzags and Central Circuits . Springer. pp. 131– 148. ISBN 9788132224495 . ^ Indelicato, G; Burkhard, P; Twarock, R (2017). "Classification of self-assembling protein nanoparticle architectures for applications in vaccine design" . Royal Society Open Science . 4 (4): 161092. Bibcode : 2017RSOS....461092I . doi : 10.1098/rsos.161092 . PMC 5414263 . PMID 28484626 . {{ cite journal }} : CS1 maint: article number as page number ( link ) CS1 maint: unflagged free DOI ( link ) ^ Kotani, M; Naito, H; Omori, T (2017). "A discrete surface theory" . Computer Aided Geometric Design . 58 : 24– 54. doi : 10.1016/j.cagd.2017.09.002 . ^ Tarnai, T. (2006). Baskets (PDF) . IASS-APCS 2006 Int. Symp. New Olympics New Shell and Spatial Structures. Beijing University of Technology: International Assoc. for Shell and Spatial Structures. pp. IL09. ^ Tarnai, T.; Kovacs, F.; Fowler, P.W.; Guest, S.D. (2012). "Wrapping the cube and other polyhedra" . Proceedings of the Royal Society A . 468 (2145): 2652. Bibcode : 2012RSPSA.468.2652T . doi : 10.1098/rspa.2012.0116 . ^ Nicodemos, Diego; Stehlík, Matěj (2018). "Packing and covering odd cycles in cubic plane graphs with small faces". European Journal of Combinatorics . 67 : 208– 221. arXiv : 1701.07748 . doi : 10.1016/j.ejc.2017.08.004 . S2CID 27137740 . ^ Goldberg, M. (1937). "A class of multi-symmetric polyhedra". Tohoku Mathematical Journal . ^ Kenner, H. (1976). Geodesic Math and How to Use It . University of California Press. ^ Caspar, D. L. D.; Klug, A. (1962). "Physical Principles in the Construction of Regular Viruses". Cold Spring Harb. Symp. Quant. Biol . 27 : 1– 24. doi : 10.1101/sqb.1962.027.001.005 . PMID 14019094 . ^ Coxeter, H.S.M. (1971). "Virus macromolecules and geodesic domes.". In Butcher, J.C. (ed.). A spectrum of mathematics . Oxford University Press. pp. 98– 107. ^ Brinkmann, G.; Goetschalckx, P.; Schein, S. (2017). "Goldberg, Fuller, Caspar, Klug and Coxeter and a general approach to local symmetry-preserving operations". Proceedings of the Royal Society A . 473 (2206): 20170267. arXiv : 1705.02848 . Bibcode : 2017RSPSA.47370267B . doi : 10.1098/rspa.2017.0267 . S2CID 119171258 . {{ cite journal }} : CS1 maint: article number as page number ( link ) ^ Deza, M; Fowler, P. W; Rassat, A; Rogers, K. M (2000). "Fullerenes as Tilings of Surfaces". Journal of Chemical Information and Computer Sciences . 40 (3): 550– 8. CiteSeerX 10.1.1.105.5973 . doi : 10.1021/ci990066h . PMID 10850758 . ^ Hirsch, Andreas; Chen, Zhongfang; Jiao, Haijun (2000). "Spherical Aromaticity in Ih Symmetrical Fullerenes: The 2(N+1)2 Rule". Angewandte Chemie . 39 (21): 3915– 3917. doi : 10.1002/1521-3773(20001103)39:21<3915::AID-ANIE3915>3.0.CO;2-O . PMID 29711706 . ^ Deza, Michel-Marie; Sikirić, Mathieu Dutour (2016). "Lego-like spheres and tori". Journal of Mathematical Chemistry . 55 (3): 752. doi : 10.1007/s10910-016-0706-8 . S2CID 125087322 . Retrieved from " https://en.wikipedia.org/w/index.php?title=Goldberg–Coxeter_construction&oldid=1048157967 " Categories : Graph operations Polyhedra Hidden categories: CS1 maint: article number as page number CS1 maint: unflagged free DOI Commons link is the pagename This page was last edited on 4 October 2021, at 15:40 (UTC) . This version of the page has been revised . Besides normal editing, the reason for revision may have been that this version contains factual inaccuracies, vandalism, outdated information, or material not compatible with the Creative Commons Attribution-ShareAlike 4.0 License . Privacy policy About Wikipedia Disclaimers Contact Wikipedia Legal & safety contacts Code of Conduct Developers Statistics Cookie statement Mobile view Search Search Toggle the table of contents Goldberg–Coxeter construction Add languages Add topic