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]
Es existieren keine 4-regulären Streichholzgraphen mit weniger als 20 Knoten.[4] Für 4-reguläre Streichholzgraphen sind Beispiele für alle Knotenzahlen ≥ 52 außer für 53, 55, 56, 58, 59, 61 und 62 bekannt, wobei die Fälle 54, 57, 65, 67, 73, 74, 77 und 85 erstmals 2016 vorgestellt wurden. Für die Knotenzahlen 52, 54, 57, 60 und 64 ist jeweils nur ein Beispiel bekannt. Von diesen fünf Graphen ist nur der mit 60 Knoten flexibel, die anderen vier sind starr.[5][6] Für die noch unbekannten Knotenzahlen von 50 bis 62 existieren sehr gute Näherungslösungen.[7] Diese finden sich auch in der Webanwendung unter „Weblinks“.
Es existieren keine regulären Streichholzgraphen mit Grad größer als 4.[4] Der kleinste 3-reguläre Streichholzgraph ohne eingeschlossene Dreiecke (Taillenweite ≥ 4) besitzt 20 Knoten und wurde 2009 von Kurz und Mazzuoccolo vorgestellt.[8] Ein Beispiel eines 3-regulären Streichholzgraphen mit Taillenweite 5 und Knotenzahl von 54 wurde 2019 von Mike Winkler, Peter Dinkelacker und Stefan Vogel vorgestellt.[9]
Das Entscheidungsproblem, welches fragt, ob ein gegebener ungerichteter planarer Graph ein Streichholzgraph ist, gehört zu den NP-schweren Problemen.[10][11]
Weblinks
- Matchstick Graphs Calculator Eine Webanwendung von Stefan Vogel zur Übersicht, Konstruktion und Berechnung von Einheitsdistanz-Graphen und Streichholzgraphen.
- Homepage von Giuseppe Mazzuoccolo an der Universität von Verona
- Homepage von Rom Pinchasi am Israel Institute of Technology
- Homepage von Sascha Kurz an der Universität Bayreuth
- Homepage von Mike Winkler (Ruhr-Universität Bochum)
Einzelnachweise
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
