Matchstick graph

Last updated
The unique smallest cubic matchstick graph Cubic matchstick graph.svg
The unique smallest cubic matchstick graph
Harborth graph
Harborth graph vector.svg
Vertices 52
Edges 104
Radius 6
Diameter 9
Girth 3
Table of graphs and parameters
3-regular girth-5 matchstick graph
Winkler 3-reg girth5 54.svg
Vertices 54
Edges 81
Girth 5
Table of graphs and parameters

In geometric graph theory, a branch of mathematics, a matchstick graph is a graph 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 which is simultaneously a unit distance graph and a plane graph. For this reason, matchstick graphs have also been called planar unit-distance graphs. [1] Informally, matchstick graphs can be made by placing noncrossing matchsticks on a flat surface, hence the name. [2]

Contents

Regular matchstick graphs

Much of the research on matchstick graphs has concerned regular graphs, in which each vertex has the same number of neighbors. This number is called the degree of the graph.

Regular matchstick graphs can have degree 0, 1, 2, 3, or 4. The complete graphs 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 placed in such a way that corresponding vertices are at unit distance from each other; its bipartite double cover is the 8-crossed prism graph. [2]

In 1986, Heiko Harborth presented the graph that became known as the Harborth Graph. It has 104 edges and 52 vertices, and, at the time, was the smallest known example of a 4-regular matchstick graph. [3] It is a rigid graph. [4]

Every 4-regular matchstick graph contains at least 20 vertices. [5] 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. [6] [7]

It is not possible for a regular matchstick graph to have degree greater than four. [5] More strongly, every -vertex matchstick graph has vertices of degree four or less. [8] The smallest 3-regular matchstick graph without triangles (girth ≥ 4) has 20 vertices, as proved by Kurz and Mazzuoccolo. [9] 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. [10]

The maximum number of edges a matchstick graph on vertices can have is . [11]

Computational complexity

It is NP-hard to test whether a given undirected planar graph can be realized as a matchstick graph. [12] [13] More precisely, this problem is complete for the existential theory of the reals. [14] Kurz (2011) 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. [15]

It is also NP-complete to determine whether a matchstick graph has a Hamiltonian cycle, even when the vertices of the graph all have integer coordinates that are given as part of the input to the problem. [16]

Combinatorial enumeration

The numbers of distinct (nonisomorphic) matchstick graphs are known for 1, 2, 3, ... up to thirteen edges; they are:

1, 1, 3, 5, 12, 28, 74, 207, 633, 2008, 6774, 23868, 87667 (sequence A066951 in the OEIS ) [17] [18]

For instance the three different graphs that can be made with three matchsticks are a claw, a triangle graph, and a three-edge path graph.

Special classes of graphs

Uniformity of edge lengths has long been seen as a desirable quality in graph drawing, [19] and some specific classes of planar graphs can always be drawn with completely uniform edges.

Every tree 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. [20]

Realization of a squaregraph as a matchstick graph Squaregraph.svg
Realization of a squaregraph as a matchstick graph

A similar property is true for squaregraphs, 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. [21]

Every matchstick graph is a unit distance graph. Penny graphs 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.

Related Research Articles

In graph theory, the girth of an undirected graph is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles, its girth is defined to be infinity. For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A graph with girth four or more is triangle-free.

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 each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

<span class="mw-page-title-main">Petersen graph</span> Cubic graph with 10 vertices and 15 edges

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

<span class="mw-page-title-main">Dual graph</span> Graph representing faces of another graph

In the mathematical discipline of graph theory, the dual graph of a planar graph G is a graph that has a vertex for each face of G. The dual graph has an edge for each pair of faces in G that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e. The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

<span class="mw-page-title-main">Gray graph</span>

In the mathematical field of graph theory, the Gray graph is an undirected bipartite graph with 54 vertices and 81 edges. It is a cubic graph: every vertex touches exactly three edges. It was discovered by Marion C. Gray in 1932 (unpublished), then discovered independently by Bouwer 1968 in reply to a question posed by Jon Folkman 1967. The Gray graph is interesting as the first known example of a cubic graph having the algebraic property of being edge but not vertex transitive.

<span class="mw-page-title-main">Midsphere</span> Sphere tangent to every edge of a polyhedron

In geometry, the midsphere or intersphere of a convex polyhedron is a sphere which is tangent to every edge of the polyhedron. Not every polyhedron has a midsphere, but the uniform polyhedra, including the regular, quasiregular and semiregular polyhedra and their duals all have midspheres. The radius of the midsphere is called the midradius. A polyhedron that has a midsphere is said to be midscribed about this sphere.

In the mathematical field of graph theory, Fáry's theorem states that any simple, planar graph can be drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as curves instead of as straight line segments does not allow a larger class of graphs to be drawn. The theorem is named after István Fáry, although it was proved independently by Klaus Wagner (1936), Fáry (1948), and Sherman K. Stein (1951).

<span class="mw-page-title-main">Unit distance graph</span> Geometric graph with unit edge lengths

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 graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs.

<span class="mw-page-title-main">Grötzsch graph</span> Triangle-free graph requiring four colors

In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, chromatic number 4, and crossing number 5. It is named after German mathematician Herbert Grötzsch, who used it as an example in connection with his 1959 theorem that planar triangle-free graphs are 3-colorable.

<span class="mw-page-title-main">Erdős–Diophantine graph</span> Complete graph on the integer plane which cannot be expanded

An Erdős–Diophantine graph is an object in the mathematical subject of Diophantine equations consisting of a set of integer points at integer distances in the plane that cannot be extended by any additional points. Equivalently, in geometric graph theory, it can be described as a complete graph with vertices located on the integer square grid such that all mutual distances between the vertices are integers, while all other grid points have a non-integer distance to at least one vertex.

<span class="mw-page-title-main">Moser spindle</span> Undirected unit-distance graph requiring four colors

In graph theory, a branch of mathematics, the Moser spindle is an undirected graph, named after mathematicians Leo Moser and his brother William, with seven vertices and eleven edges. It is a unit distance graph requiring four colors in any graph coloring, and its existence can be used to prove that the chromatic number of the plane is at least four.

<span class="mw-page-title-main">Hypohamiltonian graph</span> Type of graph in graph theory

In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G itself does not have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.

In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.

Heiko Harborth is Professor of Mathematics at Braunschweig University of Technology, 1975–present, and author of more than 188 mathematical publications. His work is mostly in the areas of number theory, combinatorics and discrete geometry, including graph theory.

<span class="mw-page-title-main">Apex graph</span> Graph which can be made planar by removing a single node

In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is an apex, not the apex because an apex graph may have more than one apex; for example, in the minimal nonplanar graphs K5 or K3,3, every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove.

In graph theory, a partial cube is a graph that is isometric to a subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial cube is the same as the distance between those vertices in the hypercube. Equivalently, a partial cube is a graph whose vertices can be labeled with bit strings of equal length in such a way that the distance between two vertices in the graph is equal to the Hamming distance between their labels. Such a labeling is called a Hamming labeling; it represents an isometric embedding of the partial cube into a hypercube.

<span class="mw-page-title-main">Apollonian network</span> Graph formed by subdivision of triangles

In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar chordal graphs, the uniquely 4-colorable planar graphs, and the graphs of stacked polytopes. They are named after Apollonius of Perga, who studied a related circle-packing construction.

<span class="mw-page-title-main">Harborth's conjecture</span> On graph drawing with integer edge lengths

In mathematics, Harborth's conjecture states that every planar graph has a planar drawing in which every edge is a straight segment of integer length. This conjecture is named after Heiko Harborth, and would strengthen Fáry's theorem on the existence of straight-line drawings for every planar graph. For this reason, a drawing with integer edge lengths is also known as an integral Fáry embedding. Despite much subsequent research, Harborth's conjecture remains unsolved.

<span class="mw-page-title-main">Penny graph</span> Graph formed by touching unit circles

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 circles can be represented physically by pennies, arranged without overlapping on a flat surface, with a vertex for each penny and an edge for each two pennies that touch.

<span class="mw-page-title-main">Golomb graph</span> Undirected unit-distance graph requiring four colors

In graph theory, the Golomb graph is a polyhedral graph with 10 vertices and 18 edges. It is named after Solomon W. Golomb, who constructed it as a unit distance graph that requires four colors in any graph coloring. Thus, like the simpler Moser spindle, it provides a lower bound for the Hadwiger–Nelson problem: coloring the points of the Euclidean plane so that each unit line segment has differently-colored endpoints requires at least four colors.

References

  1. ↑ Gervacio, Severino V.; Lim, Yvette F.; Maehara, Hiroshi (2008), "Planar unit-distance graphs having planar unit-distance complement", Discrete Mathematics, 308 (10): 1973–1984, doi: 10.1016/j.disc.2007.04.050 , MR   2394465
  2. 1 2 Weisstein, Eric W., "Matchstick graph", MathWorld
  3. ↑ Harborth, Heiko (1994), "Match sticks in the plane", in Guy, R. K.; Woodrow, R. E. (eds.), The Lighter Side of Mathematics: Proceedings of the Eugéne Strens Memorial Conference of Recreational Mathematics and its History, Calgary, Canada, 1986, Washington, D.C.: Mathematical Association of America, pp. 281–288. As cited in: Weisstein, Eric W., "Matchstick graph", MathWorld
  4. ↑ Gerbracht, Eberhard H.-A. (2011), "Symbol-crunching the Harborth graph", Advances in Applied Mathematics, 47 (2): 276–281, doi: 10.1016/j.aam.2010.09.003 , MR   2803803 . For additional details see the earlier preprint in Gerbracht, Eberhard H.-A. (2006), "Minimal Polynomials for the Coordinates of the Harborth Graph", arXiv: math/0609360 .
  5. 1 2 Kurz, Sascha; Pinchasi, Rom (2011), "Regular matchstick graphs", American Mathematical Monthly, 118 (3): 264–267, arXiv: 1401.4372 , doi:10.4169/amer.math.monthly.118.03.264, MR   2800336, S2CID   866740 .
  6. ↑ Winkler, Mike; Dinkelacker, Peter; Vogel, Stefan (2017), "New minimal (4; n)-regular matchstick graphs", Geombinatorics, 27: 26–44, arXiv: 1604.07134 .
  7. ↑ Winkler, Mike; Dinkelacker, Peter; Vogel, Stefan (2017), On the existence of 4-regular matchstick graphs, arXiv: 1705.00293 .
  8. ↑ Lavollée, Jérémy; Swanepoel, Konrad J. (2022), The number of small-degree vertices in matchstick graphs, arXiv: 2206.03956
  9. ↑ Kurz, Sascha; Mazzuoccolo, Giuseppe (2010), "3-regular matchstick graphs with given girth", Geombinatorics, 19: 156–175, arXiv: 1401.4360 .
  10. ↑ Winkler, Mike; Dinkelacker, Peter; Vogel, Stefan (2020), "A 3-regular matchstick graph of girth 5 consisting of 54 vertices", Geombinatorics, 29: 116–121, arXiv: 1903.04304 .
  11. ↑ Lavollée, Jérémy; Swanepoel, Konrad (2023-08-18), "A Tight Bound for the Number of Edges of Matchstick Graphs", Discrete & Computational Geometry, arXiv: 2209.09800 , doi: 10.1007/s00454-023-00530-z , ISSN   1432-0444
  12. ↑ Eades, Peter; Wormald, Nicholas C. (1990), "Fixed edge-length graph drawing is NP-hard", Discrete Applied Mathematics, 28 (2): 111–134, doi: 10.1016/0166-218X(90)90110-X .
  13. ↑ Cabello, Sergio; Demaine, Erik D.; Rote, Günter (2007), "Planar embeddings of graphs with specified edge lengths" (PDF), Journal of Graph Algorithms and Applications , 11 (1): 259–276, doi:10.7155/jgaa.00145 .
  14. ↑ Abel, Zachary; Demaine, Erik D.; Demaine, Martin L.; Eisenstat, Sarah; Lynch, Jayson; Schardl, Tao B. (2016), "Who needs crossings? Hardness of plane graph rigidity", in Fekete, Sándor; Lubiw, Anna (eds.), 32nd International Symposium on Computational Geometry (SoCG 2016), Leibniz International Proceedings in Informatics (LIPIcs), vol. 51, Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 3:1–3:15, doi:10.4230/LIPIcs.SoCG.2016.3, ISBN   978-3-95977-009-5 .
  15. ↑ Kurz, Sascha (2011), "Fast recognition of planar non unit distance graphs", Geombinatorics, 21 (1): 25–33, arXiv: 1401.4375 , MR   2858668 .
  16. ↑ Itai, Alon; Papadimitriou, Christos H.; Szwarcfiter, Jayme Luiz (1982), "Hamilton paths in grid graphs", SIAM Journal on Computing , 11 (4): 676–686, CiteSeerX   10.1.1.383.1078 , doi:10.1137/0211056, MR   0677661 .
  17. ↑ Salvia, Raffaele (2013), "A catalog for matchstick graphs", arXiv: 1303.5965 [math.CO]
  18. ↑ Vaisse, Alexis (2023), Matchstick graphs with up to 13 edges
  19. ↑ Fruchterman, Thomas M. J.; Reingold, Edward M. (1991), "Graph Drawing by Force-Directed Placement", Software: Practice and Experience, Wiley, 21 (11): 1129–1164, doi:10.1002/spe.4380211102, S2CID   31468174 .
  20. ↑ Carlson, Josiah; Eppstein, David (2006), "Trees with convex faces and optimal angles", in Kaufmann, Michael; Wagner, Dorothea (eds.), Proceedings of the 14th International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 4372, Springer-Verlag, pp. 77–88, arXiv: cs.CG/0607113 , doi:10.1007/978-3-540-70904-6_9, ISBN   978-3-540-70903-9, MR   2393907, S2CID   12598338 .
  21. ↑ Eppstein, David; Wortman, Kevin A. (2011), "Optimal angular resolution for face-symmetric drawings", Journal of Graph Algorithms and Applications, 15 (4): 551–564, arXiv: 0907.5474 , doi:10.7155/jgaa.00238, S2CID   10356432 .
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.