Back Unit distance graph English Graphe distance-unité French Egységtávolsággráf Hungarian 単位距離グラフ Japanese Граф единичных расстояний Russian அலகு தொலைவு கோட்டுரு Tamil Граф одиничних відстаней Ukrainian Đồ thị cạnh đơn vị Vietnamese
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.