Einheitsdistanz-Graph
# Einheitsdistanz-Graph

Ein Einheitsdistanz-Graph ist ein geometrischer Graph, bei dem jede Kante gleich lang ist. Kanten eines Einheitsdistanz-Graphen dürfen sich überschneiden, d. h. der Graph muss nicht immer planar sein. Ein Einheitsdistanz-Graph ohne Überschneidungen wird Streichholzgraph genannt.

Das Problem von Hadwiger und Nelson beschäftigt sich mit der chromatischen Zahl des Graphen. Jeder Einheitsdistanz-Graph kann mit höchstens sieben Farben eingefärbt werden, bekanntlich existieren aber auch einige Graphen, die mindestens vier Farben benötigen. Ein anderes bekanntes offenes Problem befasst sich mit der Frage, wie hoch das Verhältnis von Kanten- zu Knotenanzahl sein kann.

## Beispiele

Folgende Graphen sind Einheitsdistanz-Graphen:

* Jeder zyklische Graph
* Jeder Gittergraph
* Jeder Hyperwürfel-Graph
* Der Petersen-Graph
* Der Heawood-Graph
* Das Wagenrad $W_7$

## Strikter Einheitsdistanz-Graph

Einige Definitionen in der Literatur lassen die Möglichkeit zu, dass nicht benachbarte Knotenpaare ebenfalls Einheitsdistanz haben dürfen. Zum Beispiel gibt es eine Variante des Möbius–Kantor-Graphen von dieser Art.

Nach dieser abgeschwächten Definition sind alle verallgemeinerten Petersen-Graphen Einheitsdistanz-Graphen. Um beide Definitionen zu unterscheiden, wird ein Graph, bei dem nur benachbarte Knoten eine Einheitsdistanz haben dürfen, strikter Einheitsdistanz-Graph genannt.

Entfernt man beim Wagenrad $W_7$ eine Speiche, erhält man einen nicht-strikten Teilgraphen. Es ist nicht möglich, die Knoten und insbesondere die beiden Endpunkte der fehlenden Speiche so anzuordnen, dass man wieder einen strikten Graphen erhält.

## Zählung von Einheitsdistanzen

Paul Erdős stellte 1946 das Problem, wie man in einer Menge von n Punkten die Anzahl an Punktpaaren mit Einheitsdistanz bestimmt. Graphentheoretisch formuliert: wie dicht kann ein Einheitsdistanz-Graph sein?

Der Hyperwürfel-Graph besitzt für die Anzahl an Einheitsdistanzen eine untere Schranke proportional zu n·log n. Werden die Punkte in einem Quadratgitter mit vorsichtig gewählten Zwischenräumen angeordnet, gibt es nach Erdős eine verbesserte untere Schranke von

    $n^{1+c/\log \log n},$

Erdős bot ein Preisgeld von 500 $, falls jemand eine ähnliche Funktion für die obere Schranke findet. Die beste bekannte obere Schranke liegt bisher proportional zu

    $n^{4/3};$

Diese Grenze kann auch als Zählung der Inzidenzen zwischen Punkten und Einheitskreisen betrachtet werden, und ist nah mit dem Satz von Szemerédi und Trotter für Inzidenzen zwischen Punkten und Geraden verwandt. Das Problem (Einheitsdistanz-Problem von Erdös) ist nach wie vor offen. Erdös vermutete, dass die Anzahl der Punkte mit Einheitsdistanz in der Größenordnung der unteren Schranke war.

## Verallgemeinerung für höhere Dimensionen

Die Definition des Einheitsdistanz-Graphen kann selbstverständlich auch auf höherdimensionale euklidische Räume verallgemeinert werden. Jeder Graph kann als Punktmenge in eine genügend hohe Dimension eingebettet werden. Maehara und Vojtěch Rödl zeigten 1990, dass die notwendige Dimension um einen Graph auf diese Weise einzubetten durch den doppelten Maximalgrad des Graphen beschränkt ist.

Die notwendige Dimension um einen Graphen so einzubetten, dass alle Kanten Einheitsdistanz haben, und die notwendige Dimension um einen Graphen so einzubetten, dass alle Kanten genau den Einheitsdistanz-Paaren entsprechen, können sich stark voneinander unterscheiden: der Johnson-Graph mit 2·n Knoten kann so in die vierte Dimension eingebettet werden, dass all seine Kanten Einheitsdistanz haben, benötigt jedoch n - 2 Dimensionen für eine Einbettung, bei der nur die Kanten Einheitsdistanz-Paare sind.

