Streichholzgraph

Streichholzgraph
Der Harborth-Graph, kleinstes bekanntes Beispiel eines 4-regulären Streichholzgraphen

Ein Streichholzgraph ist in der geometrischen Graphentheorie ein in der Ebene gezeichneter Graph, bei dem alle Kanten dieselbe Länge haben und sich nicht überschneiden. Anders ausgedrückt handelt es sich dabei um einen Graphen, der gleichzeitig eine Einbettung als Einheitsdistanz-Graph und als planarer Graph hat. Der Name lässt sich darauf zurückführen, dass man solche Graphen auf einer flachen Oberfläche mit Streichhölzern nachbilden kann.[1]

Es gibt einige Streichholzgraphen, die bis zum vierten Grad regulär sind. Die vollständigen Graphen K1 und K3 sind 0-regulär bzw. 2-regulär, dagegen ist der lineare Graph P2 1-regulär. Den kleinsten 3-regulären Streichholzgraphen erhält man, indem man zwei Kopien des Diamantgraphen leicht geneigt nebeneinander auf die Spitze stellt und die Knoten mit Grad 2 jeweils durch eine Kante verbindet. Dieser Graph besitzt als bipartite Doppelüberdeckung den 8-gekreuzten Prismagraphen.[1]

1986 stellte Heiko Harborth einen Graphen mit 104 Kanten und 52 Knoten vor, der als kleinstes bekanntes Beispiel eines 4-regulären Streichholzgraphen gilt und der nach ihm den Namen Harborth-Graph trägt.[2] Dabei handelt es sich um einen starren Graphen.[3]

Man nimmt heute an, dass es keine 5-regulären Streichholzgraphen gibt. Anfang 2010 waren dafür einige Beweise im Umlauf, die jedoch noch nicht endgültig verifiziert wurden.[4][5]

Der kleinste 3-reguläre Streichholzgraph ohne eingeschlossene Dreiecke (Taillenweite ≥ 4) besitzt 20 Knoten und wurde 2009 von Kurz und Mazzuoccolo vorgestellt.[6] Diese beiden Autoren haben auch gezeigt, dass das kleinste bekannte Beispiel eines 3-regulären Streichholzgraphen mit Taillenweite 5 eine Knotenzahl von 180 besitzt.

Zu testen, ob ein gegebener ungerichteter planarer Graph ein Streichholzgraph ist, gehört zu den NP-schweren Problemen der Theoretischen Informatik.[7][8]

Einzelnachweise

  1. a b Eric W. Weisstein: Matchstick Graph. In: MathWorld. (englisch)
  2. Heiko Harborth: Match sticks in the plane. In: R. K. Guy, R. E. Woodrow (Hrsg.): 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. 1994, S. 281–288.
  3. E. H.-A. Gerbracht: Minimal polynomials for the coordinates of the Harborth graph. 2006, arXiv:math.CO/0609360.
  4. Aart Blokhuis: Regular Finite Planar Maps with Equal Edges. 2009.
  5. S. Kurz, R. Pinchasi: Regular Matchstick Graphs. 2009 (online).
  6. Sascha Kurz, Giuseppe Mazzuoccolo: 3-regular matchstick graphs with given girth. In: Geombinatorics. 19, 2009, S. 156–175.
  7. Peter Eades, Nicholas C. Wormald: Fixed edge-length graph drawing is NP-hard. In: Discrete Applied Mathematics. 28 (2), 1990, S. 111–134, doi:10.1016/0166-218X(90)90110-X.
  8. Sergio Cabello, Erik Demaine, Günter Rote: Planar embeddings of graphs with specified edge lengths. In: Journal of Graph Algorithms and Applications. 11 (1), 2007, S. 259–276 (online).

Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Streichholz — Ein entzündetes Streichholz Ein Streichholzbriefchen m …   Deutsch Wikipedia

  • Einheitsdistanz-Graph — Der Petersen Graph ist ein Einheitsdistanz Graph: er kann so gezeichnet werden, dass jede Kante gleich lang ist. Ein Einheitsdistanz Graph ist ein geometrischer Graph, bei dem jede Kante gleich lang ist. Kanten eines Einheitsdistanz Graphen… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”