The Goldberg–Coxeter construction or Goldberg–Coxeter operation (GC construction or GC operation) is a
graph operation defined on
regular polyhedral graph
In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-con ...
s with
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathematics
...
3 or 4.
It also applies to the
dual graph
In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-loop ...
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 (mathematician), Michael Goldberg (1902–1990 ...
and
geodesic polyhedra
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 polyhed ...
. The GC construction is primarily studied in
organic chemistry
Organic chemistry is a subdiscipline within chemistry involving the scientific study of the structure, properties, and reactions of organic compounds and organic materials, i.e., matter in its various forms that contain carbon atoms.Clayden, J.; ...
for its application to
fullerene
A fullerene is an allotrope of carbon whose molecule consists 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 seven atoms. The molecule may be a hollow sphere, ...
s,
but it has been applied to
nanoparticles
A nanoparticle or ultrafine particle is usually defined as a particle of matter that is between 1 and 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 1 ...
,
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, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
and
polyhedra
In geometry, a polyhedron (plural polyhedra or polyhedrons; ) is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices.
A convex polyhedron is the convex hull of finitely many points, not all on t ...
.
The Goldberg–Coxeter construction may be denoted as
, where
is the graph being operated on,
and
are integers,
, and
.
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 (1902–1990). They are defined by three pro ...
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 triangular elements of the dome are structurally rigid and distribute the structural stress throughout the structure, making geodesic dom ...
" 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 polyhed ...
, 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 emeritus p ...
and
Aaron Klug 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 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 ...
.
The discovery of
Buckminsterfullerene
Buckminsterfullerene is a type of fullerene with the formula C60. It has a cage-like fused-ring structure (truncated icosahedron) made of twenty hexagons and twelve pentagons, and resembles a soccer ball. Each of its 60 carbon atoms is bonded ...
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 Scien ...
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 formed by the complex numbers, with a Cartesian coordinate system such that the -axis, called the real axis, is formed by the real numbers, and the -axis, called the imaginary axis, is formed by the ...
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 = \f ...
. 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
. A norm,
, 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
and
are associates, then
in the Eisensteins or
in the Gaussians for some integer
. 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 a ...
, and the element of each equivalence class that has
and
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
, can be classified as follows:
* Class I:
* Class II:
* Class III: all other. Class III operators exist in chiral pairs:
is the chiral pair of
.
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
(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
is in the equivalence class of
, and for a 4-regular graph
is in the equivalence class of
. 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. Most familiar as the name o ...
and
associative.
* Complex conjugation of the element
or
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
are as follows:
# Determine the master polygon, based on
,
, and
# If operating on a 3- or 4-regular graph (instead of a graph with triangular/quadrilateral faces), take its
dual graph
In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-loop ...
. 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
is constructed on the
skeleton
A skeleton is the structural frame that supports the body of an animal. There are several types of skeletons, including the exoskeleton, which is the stable outer shell of an organism, the endoskeleton, which forms the support structure inside ...
of a
cube
In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex. Viewed from a corner it is a hexagon and its net is usually depicted as a cross.
The cube is the only r ...
. In the last two graphs, blue lines are edges of
, while black lines are edges of
. (Dotted lines are normal graph edges, just drawn differently to make overlapping graph edges more visible.) Red vertices are in
and remain in
, while blue vertices are newly created by the construction and are only in
.
File:Subdivided square 01 01.svg, Master square (1,1)
File:Hexahedron.svg, Starting polyhedron (Cube)
File:Cube skeleton.svg, , the skeleton of the cube
File:GC_1,1_Cube_faces.svg, Intermediate step of constructing .
File:Rhombic_dodecahedron_skeleton.svg, The result , after rearrangement
File:Rhombicdodecahedron.jpg, Embedding of the result (rhombic dodecahedron
In geometry, the rhombic dodecahedron is a convex polyhedron with 12 congruent rhombic faces. It has 24 edges, and 14 vertices of 2 types. It is a Catalan solid, and the dual polyhedron of the cuboctahedron.
Properties
The rhombic dodecahedro ...
)
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 can be placed on a torus such that no edges cross.
Examples
Any graph that can be embedded in a plane ...
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.
Construction
A geodesic grid is a global Earth reference that uses triangular tiles based on the subdivision of a polyhedron (usually the icosahedron, a ...
*
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). ...
*
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 3D modeling, modeling. It was devised by Edwin Catmull and James H. Clark, Jim Clark in 1978 as a generalization of b ...
*
Conway polyhedron notation
In geometry, 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 idea of using o ...
Footnotes
References
{{DEFAULTSORT:Goldberg-Coxeter construction
Graph operations
Polyhedra