Название для графика, где диск, соединяющий две точки, не содержит других точек?

Question

Проблема заключается в следующем:

Дан набор точек P на двумерной плоскости.Каждая с двумя точками (p, q) соединена ребром, если существует круг с диаметром pq, который НЕ содержит других точек из P и если p и q находятся на окружности.(таким образом, p и q - конечные точки диаметра круга)

Кто-нибудь знает, как называется этот тип графика?

Answer 1

Это называется граф Габриэля .

Я не знал этого до этого вопроса. Похоже, это связано с триангуляцией Делоне, и небольшой поиск довольно быстро нашел название. Интересно, что граф Габриэля является подграфом триангуляции Делоне.

Answer 2

Ну, это определенно планарный график, потому что в соответствии с этим определением, потому что нет никакого способа, чтобы два ребра могли пересекаться. Если бы это произошло, то хотя бы одна из конечных точек содержалась бы в окружности, определяемой другими ребрами. Чтобы доказать это, вы, вероятно, сделаете доказательство от противного (предположим, что существуют два ребра e1 и e2, которые пересекаются). Хотя я оставлю доказательство в качестве упражнения для ОП (потому что этот вид звучит как домашнее задание).