Для плоского вложения плоского графа на плоскость с прямыми ребрами определите вершину как острую вершину, если максимальный угол между двумя последовательными ребрами вокруг нее больше 180. Или, другими словами, если существует линия, проходящая через это вершина вложения так, что все ребра, попадающие в эту вершину, лежат на одной стороне линии, тогда вершина является «острой», иначе это не так. Также давайте будем беспокоиться только о вершинах со степенью не менее 3.
Я хочу рисовать плоские графики с несколькими острыми вершинами. Кто-нибудь изучал такие рисунки раньше?
В частности, я хочу нарисовать плоские графы с максимальной степенью 3, чтобы число острых вершин степени 3 во вложении было а координаты вершин можно записать с полиномиальным числом битов.
Вот что я могу найти, потратив некоторое время на Google Scholar:
Моя мера резкости вершины связана с уже изученным понятием, называемым угловым разрешением . Из Википедии:
Угловое разрешение чертежа графика относится к острейшему углу, образованному любыми двумя ребрами, которые встречаются в общей вершине чертежа.
Таким образом, для моей цели подойдет плоская схема с угловым разрешением вокруг вершин степени 3.
Для вершины со степенью на чертеже угловое разрешение вокруг нее может быть не более .2 π / д
Вопрос о том, является ли это жестким, изучался в прошлом, но я могу найти только асимптотические результаты. Например, Малиц и Папакостас доказывают, что любой плоский граф с максимальной степенью может быть нарисован с угловым разрешением . Но этот результат не дает хороших оценок для случая, когда .α d d = 3
источник
Ответы:
С другой стороны, если вам требуются более высокие уровни связности, вы можете избежать множества острых вершин. В частности, если у вас есть 3-связный планарный граф, его можно нарисовать (например, с помощью теоремы Штейница для нахождения многогранного представления и затем формирования проекции в перспективе) таким образом, что все грани выпуклые, что вызывает только внешнее лицо должно быть острым. Но каждый 3-связный планарный граф может быть встроен таким образом, чтобы внешняя грань имела не более пяти вершин (наихудший случай - додекаэдр), так что вы можете нарисовать каждый 3-связанный планарный граф (3-регулярный или нет) с помощью at самые пять острых вершин.
источник