geometric graph theory Geometric graph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geomet ...

, a branch of mathematics, a matchstick graph is a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

that can be drawn in the plane in such a way that its edges are line segments with length one that do not cross each other. That is, it is a graph that has an

embedding In mathematics, an embedding (or imbedding) is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup. When some object X is said to be embedded in another object Y, the embedding is gi ...

which is simultaneously a

unit distance graph In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graph ...

and a

plane graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...

. For this reason, matchstick graphs have also been called planar unit-distance graphs. Informally, matchstick graphs can be made by placing noncrossing

matchstick A match is a tool for starting a fire. Typically, matches are made of small wooden sticks or stiff paper. One end is coated with a material that can be ignited by friction generated by striking the match against a suitable surface. Wooden matc ...

s on a flat surface, hence the name.

Regular matchstick graphs

Much of the research on matchstick graphs has concerned

regular graph In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree o ...

s, in which each vertex has the same number of neighbors. This number is called the

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 ...

of the graph. Regular matchstick graphs can have degree 0, 1, 2, 3, or 4. The

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...

s with one, two, and three vertices (a single vertex, a single edge, and a triangle) are all matchstick graphs and are 0-, 1-, and 2-regular respectively. The smallest 3-regular matchstick graph is formed from two copies of the

diamond graph In the mathematical field of graph theory, the diamond graph is a planar, undirected graph with 4 vertices and 5 edges. It consists of a complete graph minus one edge. The diamond graph has radius 1, diameter 2, girth 3, chromat ...

placed in such a way that corresponding vertices are at unit distance from each other; its

bipartite double cover In graph theory, the bipartite double cover of an undirected graph is a bipartite, covering graph of , with twice as many vertices as . It can be constructed as the tensor product of graphs, . It is also called the Kronecker double cover, canon ...

is the 8- crossed prism graph. In 1986,

Heiko Harborth Heiko Harborth (born 11 February 1938, in Celle, Germany)Harborth's web site http://www.mathematik.tu-bs.de/harborth/ . Accessed 14 May 2009. is Professor of Mathematics at Braunschweig University of Technology, 1975–present, and author of mor ...

presented the graph that became known as the Harborth Graph. It has 104 edges and 52 vertices, and is the smallest known example of a 4- regular matchstick graph.. As cited in: It is a rigid graph. Every 4-regular matchstick graph contains at least 20 vertices.. Examples of 4-regular matchstick graphs are currently known for all number of vertices ≥ 52 except for 53, 55, 56, 58, 59, 61 and 62. The graphs with 54, 57, 65, 67, 73, 74, 77 and 85 vertices were first published in 2016. For 52, 54, 57, 60 and 64 vertices only one example is known. Of these five graphs only the one with 60 vertices is flexible, the other four are rigid. It is not possible for a regular matchstick graph to have degree greater than four. More strongly, every

n

-vertex matchstick graph has

\Omega(\sqrt n)

vertices of degree four or less. The smallest 3-regular matchstick graph without triangles (girth ≥ 4) has 20 vertices, as proved by Kurz and Mazzuoccolo. The smallest known example of a 3-regular matchstick graph of girth 5 has 54 vertices and was first presented by Mike Winkler in 2019.

Computational complexity

It is

NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

to test whether a given undirected planar graph can be realized as a matchstick graph. More precisely, this problem is complete for the

existential theory of the reals In mathematical logic, computational complexity theory, and computer science, the existential theory of the reals is the set of all true sentences of the form \exists X_1 \cdots \exists X_n \, F(X_1,\dots, X_n), where the variables X_i are interpre ...

. provides some easily tested necessary criteria for a graph to be a matchstick graph, but these are not also sufficient criteria: a graph may pass Kurz's tests and still not be a matchstick graph. It is also

NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...

to determine whether a matchstick graph has a

Hamiltonian cycle In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...

, even when the vertices of the graph all have integer coordinates that are given as part of the input to the problem.

Combinatorial enumeration

The numbers of distinct (nonisomorphic) matchstick graphs are known for 1, 2, 3, ... up to ten edges; they are: :1, 1, 3, 5, 12, 28, 74, 207, 633, 2008 For instance the three different graphs that can be made with three matchsticks are a

claw A claw is a curved, pointed appendage found at the end of a toe or finger in most amniotes (mammals, reptiles, birds). Some invertebrates such as beetles and spiders have somewhat similar fine, hooked structures at the end of the leg or tarsus ...

, a

triangle graph In the mathematical field of graph theory, the triangle graph is a planar undirected graph with 3 vertices and 3 edges, in the form of a triangle. The triangle graph is also known as the cycle graph C_3 and the complete graph K_3. Properties ...

, and a three-edge

path graph In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two terminal ...

Special classes of graphs

Uniformity of edge lengths has long been seen as a desirable quality in

graph drawing Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graph (discrete mathematics), graphs arising from applications such a ...

, and some specific classes of planar graphs can always be drawn with completely uniform edges. Every

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...

can be drawn in such a way that, if the leaf edges of the tree were replaced by infinite rays, the drawing would partition the plane into convex polygonal regions, without any crossings. For such a drawing, if the lengths of each edge are changed arbitrarily, without changing the slope of the edge, the drawing will remain planar. In particular, it is possible to choose all edges to have equal length, resulting in a realization of an arbitrary tree as a matchstick graph.

A similar property is true for

squaregraph In graph theory, a branch of mathematics, a squaregraph is a type of undirected graph that can be drawn in the plane in such a way that every bounded face is a quadrilateral and every vertex with three or fewer neighbors is incident to an unbound ...

s, the planar graphs that can be drawn in the plane in such a way that every bounded face is a quadrilateral and every vertex either lies on the unbounded face or has at least four neighbors. These graphs can be drawn with all faces parallelograms, in such a way that if a subset of edges that are all parallel to each other are lengthened or shortened simultaneously so that they continue to all have the same length, then no crossing can be introduced. In particular it is possible to normalize the edges so that they all have the same length, and obtain a realization of any squaregraph as a matchstick graph..

Related classes of graphs

Every matchstick graph is a

Penny graph In geometric graph theory, a penny graph is a contact graph of unit circles. It is formed from a collection of unit circles that do not cross each other, by creating a vertex for each circle and an edge for every pair of tangent circles. The circ ...

s are the graphs that can be represented by tangencies of non-overlapping unit circles. Every penny graph is a matchstick graph. However, some matchstick graphs (such as the eight-vertex cubic matchstick graph of the first illustration) are not penny graphs, because realizing them as a matchstick graph causes some non-adjacent vertices to be closer than unit distance to each other.

References

{{DEFAULTSORT:Matchstick Graph Geometric graphs