HOME

TheInfoList



OR:

The Goldberg–Coxeter construction or Goldberg–Coxeter operation (GC construction or GC operation) is a graph operation defined on
regular Regular may refer to: Arts, entertainment, and media Music * "Regular" (Badfinger song) * Regular tunings of stringed instruments, tunings with equal intervals between the paired notes of successive open strings Other uses * Regular character, ...
polyhedral graph In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the Vertex (geometry), vertices and Edge (geometry), edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyh ...
s with degree 3 or 4. It also applies to the
dual graph In the mathematics, mathematical discipline of graph theory, the dual graph of a planar graph is a graph that has a vertex (graph theory), vertex for each face (graph theory), face of . The dual graph has an edge (graph theory), edge for each p ...
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 In mathematics, and more specifically in polyhedral combinatorics, a Goldberg polyhedron is a convex polyhedron made from hexagons and pentagons. They were first described in 1937 by Michael Goldberg (1902–1990). They are defined by three prop ...
and
geodesic polyhedra A geodesic polyhedron is a convex polyhedron made from triangle (geometry), triangles. They usually have icosahedral symmetry, such that they have 6 triangles at a Vertex (geometry), vertex, except 12 vertices which have 5 triangles. They are ...
. The GC construction is primarily studied in
organic chemistry Organic chemistry is a subdiscipline within chemistry involving the science, scientific study of the structure, properties, and reactions of organic compounds and organic matter, organic materials, i.e., matter in its various forms that contain ...
for its application to
fullerene A fullerene is an allotropes of carbon, allotrope of carbon whose molecules consist of carbon atoms connected by single and double bonds so as to form a closed or partially closed mesh, with fused rings of five to six atoms. The molecules may ...
s, but it has been applied to
nanoparticles A nanoparticle or ultrafine particle is a particle of matter 1 to 100 nanometres (nm) in diameter. The term is sometimes used for larger particles, up to 500 nm, or fibers and tubes that are less than 100 nm in only two directions. At ...
,
computer-aided design Computer-aided design (CAD) is the use of computers (or ) to aid in the creation, modification, analysis, or optimization of a design. This software is used to increase the productivity of the designer, improve the quality of design, improve c ...
,
basket weaving Basket weaving (also basketry or basket making) is the process of weaving or sewing pliable materials into three-dimensional artifacts, such as baskets, mats, mesh bags or even furniture. Craftspeople and artists specialized in making baskets ...
, and the general study of
graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
and
polyhedra In geometry, a polyhedron (: polyhedra or polyhedrons; ) is a three-dimensional figure with flat polygonal faces, straight edges and sharp corners or vertices. The term "polyhedron" may refer either to a solid figure or to its boundary su ...
. The Goldberg–Coxeter construction may be denoted as GC_(G_0), where G_0 is the graph being operated on, k and l are integers, k >0, and \ell \ge 0.


History

Michael Goldberg introduced the
Goldberg polyhedron In mathematics, and more specifically in polyhedral combinatorics, a Goldberg polyhedron is a convex polyhedron made from hexagons and pentagons. They were first described in 1937 by Michael Goldberg (mathematician), Michael Goldberg (1902–1990 ...
in 1937.
Buckminster Fuller Richard Buckminster Fuller (; July 12, 1895 – July 1, 1983) was an American architect, systems theorist, writer, designer, inventor, philosopher, and futurist. He styled his name as R. Buckminster Fuller in his writings, publishing more t ...
coined the term "
geodesic dome A geodesic dome is a hemispherical thin-shell structure (lattice-shell) based on a geodesic polyhedron. The rigid triangular elements of the dome distribute stress throughout the structure, making geodesic domes able to withstand very heavy ...
" in the 1940s, although he largely kept the mathematics behind the domes a trade secret. 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 A geodesic polyhedron is a convex polyhedron made from triangles. They usually have icosahedral symmetry, such that they have 6 triangles at a vertex, except 12 vertices which have 5 triangles. They are the dual of corresponding Goldberg po ...
, dual to the Goldberg polyhedron. In 1962,
Donald Caspar Donald L. D. Caspar (January 8, 1927 – November 27, 2021) was an American structural biologist (the very term he coined) known for his works on the structures of biological molecules, particularly of the tobacco mosaic virus. He was an emeritu ...
and
Aaron Klug Sir Aaron Klug (11 August 1926 – 20 November 2018) was a British biophysicist and chemist. He was a winner of the 1982 Nobel Prize in Chemistry for his development of crystallographic electron microscopy and his structural elucidation of biol ...
published an article on the geometry of
viral capsid A capsid is the protein shell of a virus, enclosing its genetic material. It consists of several oligomeric (repeating) structural subunits made of protein called protomers. The observable 3-dimensional morphological subunits, which may or ma ...
s that applied and expanded upon concepts from Goldberg and Fuller.
H.S.M. Coxeter Harold Scott MacDonald "Donald" Coxeter (9 February 1907 – 31 March 2003) was a British-Canadian geometer and mathematician. He is regarded as one of the greatest geometers of the 20th century. Coxeter was born in England and educated ...
published an article in 1971 covering much of the same information. 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 Stigler's law of eponymy, proposed by University of Chicago statistics professor Stephen Stigler in his 1980 publication "Stigler's law of eponymy", states that "no scientific discovery is named after its original discoverer." Examples include H ...
. The discovery of
Buckminsterfullerene Buckminsterfullerene is a type of fullerene with the formula . It has a cage-like fused-ring structure ( truncated icosahedron) made of twenty hexagons and twelve pentagons, and resembles a football. Each of its 60 carbon atoms is bonded to i ...
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 Michel Marie Deza (27 April 1939. – 23 November 2016) was a Soviet and French mathematician, specializing in combinatorics, discrete geometry and graph theory. He was the retired director of research at the French National Centre for Scient ...
in 2000. This is also the first time the degree 4 case was considered.


Construction

This section largely follows Deza et al.'s two articles.


Master polygons

Regular lattices over the
complex plane In mathematics, the complex plane is the plane (geometry), plane formed by the complex numbers, with a Cartesian coordinate system such that the horizontal -axis, called the real axis, is formed by the real numbers, and the vertical -axis, call ...
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 In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as \mathbf /ma ...
, and the 3-regular case uses triangular lattice over the
Eisenstein integers In mathematics, the Eisenstein integers (named after Gotthold Eisenstein), occasionally also known as Eulerian integers (after Leonhard Euler), are the complex numbers of the form : z = a + b\omega , where and are integers and : \omega = \frac ...
. For convenience, an alternate parameterization of the Eisenstein integers is used, based on the sixth root of unity instead of the third. The usual definition of Eisenstein integers uses the element \omega = \frac\left(-1 + i\sqrt\right) = e^ = u - 1. A norm, t(k, \ell), is defined as the square of the absolute value of the
complex number In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the for ...
. 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 and y are associates, then x=u^n y in the Eisensteins or x=i^n y in the Gaussians for some integer n. The set of elements that are associates of each other is an
equivalence class In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements ...
, and the element of each equivalence class that has a>0 and b\ge0 is the normal form. File:Breakdown 3 2 tri.svg, (3,2) master triangle over triangular grid File:Subdivided square 3 2 with explanation.svg, (3,2) master square over square grid Master polygons, and the operator GC_\left(G_0\right), can be classified as follows: * Class I: \ell = 0. * Class II: k = \ell. * Class III: all other. Class III operators exist in chiral pairs: GC_\left(G_0\right) is the chiral pair of GC_(G_0). 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 polygons for squares

Composition of Goldberg–Coxeter operations corresponds to multiplication of complex numbers. If and only if GC_\left(GC_\left(G_0\right)\right) = GC_\left(G_0\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 + bu)(c + du) is in the equivalence class of (e + fu), and for a 4-regular graph (a + bi)(c + di) is in the equivalence class of (e + fi). There are some useful consequences of this: * The application of repeated Goldberg–Coxeter operations is
commutative In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Perhaps most familiar as a pr ...
and
associative In mathematics, the associative property is a property of some binary operations that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement for express ...
. * Complex conjugation of the element a + bi or a + bu corresponds to reflection of the constructed graph. * Since the Gaussian integers and Euclidean integers are both
Euclidean domain In mathematics, more specifically in ring theory, a Euclidean domain (also called a Euclidean ring) is an integral domain that can be endowed with a Euclidean function which allows a suitable generalization of Euclidean division of integers. Th ...
s, 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 GC_(G_0)are as follows: # Determine the master polygon, based on k, \ell, and G_0 # If operating on a 3- or 4-regular graph (instead of a graph with triangular/quadrilateral faces), take its
dual graph In the mathematics, mathematical discipline of graph theory, the dual graph of a planar graph is a graph that has a vertex (graph theory), vertex for each face (graph theory), face of . The dual graph has an edge (graph theory), edge for each p ...
. 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 GC_(G_0) is constructed on the
skeleton A skeleton is the structural frame that supports the body of most animals. There are several types of skeletons, including the exoskeleton, which is a rigid outer shell that holds up an organism's shape; the endoskeleton, a rigid internal fra ...
of a
cube A cube or regular hexahedron is a three-dimensional space, three-dimensional solid object in geometry, which is bounded by six congruent square (geometry), square faces, a type of polyhedron. It has twelve congruent edges and eight vertices. It i ...
. In the last two graphs, blue lines are edges of G_0, while black lines are edges of GC_(G_0). (Dotted lines are normal graph edges, just drawn differently to make overlapping graph edges more visible.) Red vertices are in G_0 and remain in GC_(G_0), while blue vertices are newly created by the construction and are only in GC_(G_0). File:Subdivided square 01 01.svg, Master square (1,1) File:Hexahedron.svg, Starting polyhedron (Cube) File:Cube skeleton.svg, G_0, the skeleton of the cube File:GC_1,1_Cube_faces.svg, Intermediate step of constructing GC_(G_0). File:Rhombic_dodecahedron_skeleton.svg, The result GC_(G_0), after rearrangement File:Rhombicdodecahedron.jpg, Embedding of the result (
rhombic dodecahedron In geometry, the rhombic dodecahedron is a Polyhedron#Convex_polyhedra, convex polyhedron with 12 congruence (geometry), congruent rhombus, rhombic face (geometry), faces. It has 24 edge (geometry), edges, and 14 vertex (geometry), vertices of 2 ...
)


Extensions

The Goldberg–Coxeter construction can be easily extended to some non-planar graphs, such as
toroidal graph In the mathematical field of graph theory, a toroidal graph is a graph that can be embedded on a torus. In other words, the graph's vertices and edges can be placed on a torus such that no edges intersect except at a vertex that belongs to bo ...
s. 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

*
Geodesic grid A geodesic grid is a spatial grid based on a geodesic polyhedron or Goldberg polyhedron. History The earliest use of the (icosahedral) geodesic grid in geophysical modeling dates back to 1968 and the work by Sadourny, Arakawa, and Mintz and Will ...
*
Quadrilateralized spherical cube In mapmaking, a quadrilateralized spherical cube, or quad sphere for short, is an equal-area polyhedral map projection and discrete global grid scheme for data collected on a spherical surface (either that of the Earth or the celestial sphere). I ...
*
Loop subdivision surface In computer graphics, the Loop method for subdivision surfaces is an approximating subdivision scheme developed by Charles Loop in 1987 for triangular meshes. Prior methods, namely Catmull-Clark and Doo-Sabin (1978), focused on quad meshes. L ...
*
Catmull–Clark subdivision surface The Catmull–Clark algorithm is a technique used in 3D computer graphics to create curved surfaces by using subdivision surface modeling. It was devised by Edwin Catmull and Jim Clark in 1978 as a generalization of bi-cubic ''uniform'' B-splin ...
*
Conway polyhedron notation In geometry and topology, Conway polyhedron notation, invented by John Horton Conway and promoted by George W. Hart, is used to describe polyhedra based on a seed polyhedron modified by various prefix operations. Conway and Hart extended the i ...


Footnotes


References

{{DEFAULTSORT:Goldberg-Coxeter construction Graph operations Polyhedra