Matchstick graph
Graph with edges of length one, able to be drawn without crossings
title: "Matchstick graph" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["geometric-graphs", "planar-graphs"] description: "Graph with edges of length one, able to be drawn without crossings" topic_path: "general/geometric-graphs" source: "https://en.wikipedia.org/wiki/Matchstick_graph" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0
::summary Graph with edges of length one, able to be drawn without crossings ::
::data[format=table title="infobox graph"]
| Field | Value |
|---|---|
| name | Harborth graph |
| image | [[File:Harborth graph vector.svg |
| vertices | 52 |
| edges | 104 |
| radius | 6 |
| girth | 3 |
| diameter | 9 |
| automorhisms | 4 |
| :: |
::figure[src="https://upload.wikimedia.org/wikipedia/commons/e/ef/Cubic_matchstick_graph.svg" caption="cubic]] matchstick graph"] ::
| name = Harborth graph | image = [[File:Harborth graph vector.svg|220px]] | vertices = 52 | edges = 104 | radius = 6 | girth = 3 | diameter = 9 | automorhisms = 4 | name = 3-regular girth-5 matchstick graph | image = [[File:Winkler 3-reg girth5 54.svg||220px]] | vertices = 54 | edges = 81 | girth = 5
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. Informally, matchstick graphs can be made by placing noncrossing matchsticks on a flat surface, hence the name.
Matchstick graphs have also been called planar unit-distance graphs.{{citation | last1 = Gervacio | first1 = Severino V. | last2 = Lim | first2 = Yvette F. | last3 = Maehara | first3 = Hiroshi | doi = 10.1016/j.disc.2007.04.050 | issue = 10 | journal = Discrete Mathematics | mr = 2394465 | pages = 1973–1984 | title = Planar unit-distance graphs having planar unit-distance complement | volume = 308 | year = 2008| doi-access = free Some graphs have both non-crossing embeddings with non-unit vertex distances and unit-distance embeddings with crossings; these are planar unit-distance graphs but are not matchstick graphs. An example is the Dürer graph.{{citation | last1 = Horvat | first1 = Boris | last2 = Pisanski | first2 = Tomaž | last3 = Žitnik | first3 = Arjana | issue = 4 | journal = Croatica Chemica Acta | pages = 771–779 | title = The dilation coefficient of complete graphs | url = https://hrcak.srce.hr/45617 | volume = 82 | year = 2009}}
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.
In 1986, Heiko Harborth presented the graph that became known as the Harborth Graph. It has 104 edges and 52 vertices and is currently the smallest known example of a 4-regular matchstick graph.{{citation | last = Harborth | first = Heiko | author-link = Heiko Harborth | contribution = Match sticks in the plane | editor1-last = Guy | editor1-first = R. K. | editor2-last = Woodrow | editor2-first = R. E. | location = Washington, D.C. | pages = 281–288 | publisher = Mathematical Association of America | title = The Lighter Side of Mathematics: Proceedings of the Eugéne Strens Memorial Conference of Recreational Mathematics and its History, Calgary, Canada, 1986 | year = 1994}}. As cited in: It is a rigid graph.{{citation | last = Gerbracht | first = Eberhard H.-A. | doi = 10.1016/j.aam.2010.09.003 | issue = 2 | journal = Advances in Applied Mathematics | mr = 2803803 | pages = 276–281 | title = Symbol-crunching the Harborth graph | volume = 47 | year = 2011| doi-access = free
Every 4-regular matchstick graph contains at least 20 vertices.{{citation | last1 = Kurz | first1 = Sascha | last2 = Pinchasi | first2 = Rom | doi = 10.4169/amer.math.monthly.118.03.264 | issue = 3 | journal = American Mathematical Monthly | mr = 2800336 | pages = 264–267 | title = Regular matchstick graphs | volume = 118 | year = 2011 | arxiv = 1401.4372 | s2cid = 866740 | last1 = Winkler | first1 = Mike | last2 = Dinkelacker | first2 = Peter | last3 = Vogel | first3 = Stefan | title = New minimal (4; n)-regular matchstick graphs | arxiv = 1604.07134 | journal = Geombinatorics | volume = 27 | pages = 26–44 | year = 2017}}. | last1 = Winkler | first1 = Mike | last2 = Dinkelacker | first2 = Peter | last3 = Vogel | first3 = Stefan | title = On the existence of 4-regular matchstick graphs | arxiv = 1705.00293 | year = 2017}}.
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.{{citation | last1 = Lavollée | first1 = Jérémy | last2 = Swanepoel | first2 = Konrad J. | arxiv = 2206.03956 | journal = The Australasian Journal of Combinatorics | mr = 4515475 | pages = 92–99 | title = The number of small-degree vertices in matchstick graphs | volume = 85 | year = 2023}} The smallest 3-regular matchstick graph without triangles (girth ≥ 4) has 20 vertices, as proved by Kurz and Mazzuoccolo.{{citation | last1 = Kurz | first1 = Sascha | last2 = Mazzuoccolo | first2 = Giuseppe | title = 3-regular matchstick graphs with given girth | arxiv = 1401.4360 | journal = Geombinatorics | volume = 19 | pages = 156–175 | year = 2010}}. 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.{{citation | last1 = Winkler | first1 = Mike | last2 = Dinkelacker | first2 = Peter | last3 = Vogel | first3 = Stefan | title = A 3-regular matchstick graph of girth 5 consisting of 54 vertices | arxiv = 1903.04304 | journal = Geombinatorics | volume = 29 | pages = 116–121 | year = 2020}}.
The maximum number of edges a matchstick graph on n vertices can have is \left\lfloor 3n - \sqrt{12n-3}\right\rfloor.
Computational complexity
It is NP-hard to test whether a given undirected planar graph can be realized as a matchstick graph.{{citation | last1 = Eades | first1 = Peter | author1-link = Peter Eades | last2 = Wormald | first2 = Nicholas C. | doi = 10.1016/0166-218X(90)90110-X | issue = 2 | journal = Discrete Applied Mathematics | pages = 111–134 | title = Fixed edge-length graph drawing is NP-hard | volume = 28 | year = 1990| doi-access = free | last1 = Cabello | first1 = Sergio | last2 = Demaine | first2 = Erik D. | author2-link = Erik Demaine | last3 = Rote | first3 = Günter | issue = 1 | journal = Journal of Graph Algorithms and Applications | pages = 259–276 | title = Planar embeddings of graphs with specified edge lengths | url = https://www.cs.brown.edu/sites/jgaa/accepted/2007/CabelloDemaineRote2007.11.1.pdf | volume = 11 | year = 2007 | doi=10.7155/jgaa.00145}}. More precisely, this problem is complete for the existential theory of the reals.{{citation | last1 = Abel | first1 = Zachary | last2 = Demaine | first2 = Erik D. | author2-link = Erik Demaine | last3 = Demaine | first3 = Martin L. | author3-link = Martin Demaine | last4 = Eisenstat | first4 = Sarah | last5 = Lynch | first5 = Jayson | last6 = Schardl | first6 = Tao B. | editor1-last = Fekete | editor1-first = Sándor | editor2-last = Lubiw | editor2-first = Anna | contribution = Who needs crossings? Hardness of plane graph rigidity | doi = 10.4230/LIPIcs.SoCG.2016.3 | isbn = 978-3-95977-009-5 | location = Dagstuhl, Germany | pages = 3:1–3:15 | publisher = Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik | series = Leibniz International Proceedings in Informatics (LIPIcs) | title = 32nd International Symposium on Computational Geometry (SoCG 2016) | volume = 51 | year = 2016| doi-access = free | last = Kurz | first = Sascha | arxiv = 1401.4375 | issue = 1 | journal = Geombinatorics | mr = 2858668 | pages = 25–33 | title = Fast recognition of planar non unit distance graphs | volume = 21 | year = 2011}}.
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.{{citation | last1 = Itai | first1 = Alon | last2 = Papadimitriou | first2 = Christos H. | author2-link = Christos Papadimitriou | last3 = Szwarcfiter | first3 = Jayme Luiz | doi = 10.1137/0211056 | issue = 4 | journal = SIAM Journal on Computing | mr = 677661 | pages = 676–686 | title = Hamilton paths in grid graphs | volume = 11 | year = 1982| citeseerx = 10.1.1.383.1078
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 {{cite arXiv | last = Salvia | first = Raffaele | year = 2013 | title = A catalog for matchstick graphs | class = math.CO | eprint = 1303.5965 | mode=cs2 | last1 = Vaisse | first1 = Alexis | url=http://alexis.vaisse.monsite-orange.fr/ | title = Matchstick graphs with up to 13 edges | year = 2023 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,{{citation | last1=Fruchterman | first1=Thomas M. J. | last2=Reingold | first2=Edward M. | author2-link = Edward Reingold | title=Graph Drawing by Force-Directed Placement | year=1991 | journal=Software: Practice and Experience | publisher=Wiley | volume=21 | issue=11 | pages=1129–1164 | doi=10.1002/spe.4380211102| s2cid=31468174
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.{{citation | last1 = Carlson | first1 = Josiah | last2 = Eppstein | first2 = David | editor1-last = Kaufmann | editor1-first = Michael | editor2-last = Wagner | editor2-first = Dorothea | arxiv = cs.CG/0607113 | contribution = Trees with convex faces and optimal angles | doi = 10.1007/978-3-540-70904-6_9 | mr = 2393907 | pages = 77–88 | publisher = Springer-Verlag | series = Lecture Notes in Computer Science | title = Proceedings of the 14th International Symposium on Graph Drawing | volume = 4372 | year = 2006| isbn = 978-3-540-70903-9 | s2cid = 12598338
::figure[src="https://upload.wikimedia.org/wikipedia/commons/f/f8/Squaregraph.svg" caption="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. This makes it possible to normalize the edges so that they all have the same length, and obtain a realization of any squaregraph as a matchstick graph.{{citation | last1 = Eppstein | first1 = David | last2 = Wortman | first2 = Kevin A. | arxiv = 0907.5474 | doi = 10.7155/jgaa.00238 | issue = 4 | journal = Journal of Graph Algorithms and Applications | pages = 551–564 | title = Optimal angular resolution for face-symmetric drawings | volume = 15 | year = 2011| s2cid = 10356432
Related classes of graphs
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.
References
References
- {{mathworld. MatchstickGraph
- (2023-08-18). "A Tight Bound for the Number of Edges of Matchstick Graphs". Discrete & Computational Geometry.
::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::