Граф Уркгарта множини точок на площині, названий на честь Родеріка Б. Уркгарта, отримують видаленням найдовшої сторони з кожного трикутника в тріангуляції Делоне.

Граф описав Уркгарт^[1], який припустив, що видалення найдовшої сторони з кожного трикутника Делоне було б швидким способом побудови графа відносних околів (граф, що з'єднує пари точок p і q, якщо не існує третьої точки r, яка ближча до p і q, ніж до решти). Оскільки тріангуляцію Делоне можна побудувати за час ${\displaystyle O(n\log n)}$, така сама межа існує для графа Уркгарта^[2]. Хоча пізніше показано, що граф Уркгарта не точно те саме, що граф відносних околів^[3], його можна використати як хороше наближення до цього графа^[4]. Задачу побудови графів відносних околів за час ${\displaystyle O(n\log n)}$, що стала відкритою після виявлення невідповідності між графом Уркгарта і графом відносних околів, розв'язав Суповіт^[5][6].

Подібно до графів відносних околів, граф Уркгарта множини точок у загальному положенні містить евклідове мінімальне кістякове дерево цих точок, звідки випливає, що цей граф зв'язний.