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
, 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 (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
. A norm,
, 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
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 ...
, 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. 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
or
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
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 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
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
, 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 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