Matchstick graph

Harborth graph
Vertices 52
Edges 104
Radius 6
Diameter 9
Girth 3

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.[1]

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.

It is known that there are matchstick graphs that are regular of any degree up to 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.[1]

In 1986, Heiko Harborth presented the graph that would bear his name, the Harborth Graph. With 104 edges and 52 vertices, is the smallest known example of a 4-regular matchstick graph.[2] It is a rigid graph.[3]

It is not possible for a regular matchstick graph to have degree greater than four.[4]

The smallest 3-regular matchstick graph without triangles (girth ≥ 4) has 20 vertices, as proved by Kurz and Mazzuoccolo.[5] Furthermore, they exhibit the smallest known example of a 3-regular matchstick graph of girth 5 (180 vertices).

Computational complexity

Unsolved problem in mathematics:
Can matchstick graphs be recognized in NP?
(more unsolved problems in mathematics)

It is NP-hard to test whether a given undirected planar graph can be realized as a matchstick graph.[6][7] However, the references that prove this do not show whether the problem belongs to NP, and the closely related problem of recognizing nonplanar unit distance graphs is complete for the existential theory of the reals, a somewhat larger class. Determining whether matchstick graph recognition belongs to NP (in which case it would be NP-complete), whether it is instead \exists\mathbb{R}-complete, or whether it is somewhere between these two extremes remains an open problem.[8] Kurz (2014) 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.[9]

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.[10]

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 (sequence A066951 in OEIS)[11][12]

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,[13] 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.[14]

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.[15]

References

  1. 1 2 Weisstein, Eric W., "Matchstick graph", MathWorld.
  2. ↑ Harborth, Heiko (1994), "Match sticks in the plane", in Guy, R. K.; Woodrow, R. E., 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.
  3. ↑ Gerbracht, E. H.-A. (2006), Minimal polynomials for the coordinates of the Harborth graph, arXiv:math.CO/0609360
  4. ↑ Kurz, Sascha; Pinchasi, Rom (2011), "Regular matchstick graphs", American Mathematical Monthly 118 (3): 264–267, doi:10.4169/amer.math.monthly.118.03.264, MR 2800336.
  5. ↑ Kurz, Sascha; Mazzuoccolo, Giuseppe (2010), "3-regular matchstick graphs with given girth", Geombinatorics 19: 156–175, arXiv:1401.4360.
  6. ↑ 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.
  7. ↑ 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.
  8. ↑ Schaefer, Marcus (2013), "Realizability of graphs and linkages", in Pach, János, Thirty Essays on Geometric Graph Theory, Springer, pp. 461–482, doi:10.1007/978-1-4614-0110-0_24.
  9. ↑ Kurz, Sascha (2014), Fast recognition of planar non unit distance graphs, arXiv:1401.4375.
  10. ↑ Itai, Alon; Papadimitriou, Christos H.; Szwarcfiter, Jayme Luiz (1982), "Hamilton paths in grid graphs", SIAM Journal on Computing 11 (4): 676–686, doi:10.1137/0211056, MR 677661.
  11. ↑ Salvia, Raffaele (2013), A catalog for matchstick graphs, arXiv:1303.5965
  12. ↑ Vaisse, Alexis (2015). "Matchstick graphs with up to 10 edges".
  13. ↑ Fruchterman, Thomas M. J.; Reingold, Edward M. (1991), "Graph Drawing by Force-Directed Placement", Software – Practice & Experience (Wiley) 21 (11): 1129–1164, doi:10.1002/spe.4380211102.
  14. ↑ Carlson, Josiah; Eppstein, David (2006), "Trees with convex faces and optimal angles", in Kaufmann, Michael; Wagner, Dorothea, Proc. 14th Int. Symp. Graph Drawing, Lecture Notes in Computer Science 4372, Springer-Verlag, pp. 77–88, arXiv:cs.CG/0607113, doi:10.1007/978-3-540-70904-6_9, MR 2393907.
  15. ↑ Eppstein, David; Wortman, Kevin A. (2011), "Optimal angular resolution for face-symmetric drawings", J. Graph Algorithms & Applications 15 (4): 551–564, arXiv:0907.5474, doi:10.7155/jgaa.00238.
This article is issued from Wikipedia - version of the Monday, April 11, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.