Match graph

from Wikipedia, the free encyclopedia
The Harborth graph, the smallest known example of a 4-regular matchstick graph

A matchstick graph is in the geometric graph theory , a drawn in the plane graph in which all edges have the same length and do not overlap. In other words, it is a graph that is simultaneously embedded as a unit distance graph and as a planar graph . The name can be traced back to the fact that such graphs can be reproduced on a flat surface with matches .

There are some matchstick graphs that are regular up to fourth grade . The complete graphs K 1 and K 3 are 0-regular and 2-regular, respectively, whereas the linear graph P 2 is 1-regular. The smallest 3-regular matchstick graph is obtained by placing two copies of the diamond graph slightly inclined next to each other on the tip and connecting the nodes with degree 2 each with an edge. This graph has the 8- crossed prism graph as a bipartite double cover .

In 1986 Heiko Harborth presented a graph with 104 edges and 52 nodes, which is the smallest known example of a 4-regular matchstick graph and which bears the name Harborth graph after him . This is a rigid graph .

There are no 4-regular matchstick graphs with less than 20 knots. For 4-regular matchstick graphs, examples are known for all node numbers ≥ 52 except for 53, 55, 56, 58, 59, 61 and 62, with cases 54, 57, 65, 67, 73, 74, 77 and 85 being presented for the first time in 2016 were. Only one example is known for the node numbers 52, 54, 57, 60 and 64. Of these five graphs, only the one with 60 nodes is flexible, the other four are rigid.

4-regular matchstick graph with 54 knots
4-regular match graph with 57 knots
4-regular match graph with 60 knots

There are no regular matchstick graphs with degrees greater than 4. The smallest 3-regular matchstick graph without enclosed triangles ( waist size ≥ 4) has 20 nodes and was presented in 2009 by Kurz and Mazzuoccolo. An example of a 3-regular matchstick graph with a waist size of 5 and a knot number of 54 was presented in 2019 by Mike Winkler, Peter Dinkelacker and Stefan Vogel.

Smallest known example of a 3-regular matchstick graph with waist size 5

The decision problem , which asks whether a given undirected planar graph is a matchstick graph, belongs to the NP-hard problems.

Individual evidence

  1. ↑ a b Eric W. Weisstein : Matchstick Graph . In: MathWorld (English).
  2. ↑ Heiko Harborth : Match sticks in the plane . In: RK Guy, RE Woodrow (Ed.): The Lighter Side of Mathematics: Proceedings of the Eugéne Strens Memorial Conference of Recreational Mathematics and its History, Calgary, Canada, 1986 . Mathematical Association of America , Washington DC 1994, p.  281-288 .
  3. ↑ EH-A. Gerbracht: Minimal polynomials for the coordinates of the Harborth graph . 2006, arxiv : math.CO/0609360 .
  4. ↑ a b Sascha Kurz, Rome Pinchasi: Regular matchstick graphs . In: American Mathematical Monthly . 118, No. 3, 2011, pp. 264-267. doi : 10.4169 / amer.math.monthly.118.03.264 . .
  5. ↑ Mike Winkler, Peter Dinkelacker, Stefan Vogel: New minimal (4; n) -regular matchstick graphs . In: Geombinatorics . tape 27 , 2017, p. 26-44 .
  6. ↑ Sascha Kurz, Giuseppe Mazzuoccolo: 3-regular matchstick graphs with given girth . In: Geombinatorics . tape 19 , 2009, p. 156-175 .
  7. ↑ Mike Winkler, Peter Dinkelacker, Stefan Vogel: A 3-regular matchstick graph of girth 5 consisting of 54 vertices . In: Geombinatorics . tape 29 , 2020, p. 116-121 , arxiv : 1903.04304 [math.CO] .
  8. ^ Peter Eades, Nicholas C. Wormald: Fixed edge-length graph drawing is NP-hard . In: Discrete Applied Mathematics . tape 28 (2) , 1990, pp. 111-134 , doi : 10.1016 / 0166-218X (90) 90110-X .
  9. ^ Sergio Cabello, Erik Demaine , Günter Rote: Planar embeddings of graphs with specified edge lengths . In: Journal of Graph Algorithms and Applications . tape 11 (1) , 2007, pp. 259–276 ( online (PDF; 2.8 MB)).