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 is currently 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. 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. [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 a 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">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.

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, Fáry, and Sherman K. Stein.

<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">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">Laman graph</span>

In graph theory, the Laman graphs are a family of sparse graphs describing the minimally rigid systems of rods and joints in the plane. Formally, a Laman graph is a graph on n vertices such that, for all k, every k-vertex subgraph has at most 2k − 3 edges, and such that the whole graph has exactly 2n − 3 edges. Laman graphs are named after Gerard Laman, of the University of Amsterdam, who in 1970 used them to characterize rigid planar structures. However, this characterization, the Geiringer–Laman theorem, had already been discovered in 1927 by Hilda Geiringer.

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

<span class="mw-page-title-main">Halin graph</span> Mathematical tree with cycle through leaves

In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross, and the cycle connects the leaves in their clockwise ordering in this embedding. Thus, the cycle forms the outer face of the Halin graph, with the tree inside it.

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.

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

In graph theory, the thickness of a graph G is the minimum number of planar graphs into which the edges of G can be partitioned. That is, if there exists a collection of k planar graphs, all having the same set of vertices, such that the union of these planar graphs is G, then the thickness of G is at most k. In other words, the thickness of a graph is the minimum number of planar subgraphs whose union equals to graph G.

<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">Locally linear graph</span> Graph where every edge is in one triangle

In graph theory, a locally linear graph is an undirected graph in which every edge belongs to exactly one triangle. Equivalently, for each vertex of the graph, its neighbors are each adjacent to exactly one other neighbor, so the neighbors can be paired up into an induced matching. Locally linear graphs have also been called locally matched graphs. Their triangles form the hyperedges of triangle-free 3-uniform linear hypergraphs and the blocks of certain partial Steiner triple systems, and the locally linear graphs are exactly the Gaifman graphs of these hypergraphs or partial Steiner systems.

In graph theory, a geodetic graph is an undirected graph such that there exists a unique (unweighted) shortest path between each two vertices.

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. (2023), "The number of small-degree vertices in matchstick graphs", The Australasian Journal of Combinatorics, 85: 92–99, arXiv: 2206.03956 , MR   4515475
  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, 21 (11), Wiley: 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.