Проверка на внешнюю планарность в графе с помощью BOOST?

Question

Я просто концептуально хочу знать, как проверить, является ли график внешнепланарным или нет. Я знаю, что вы можете проверить планарность на графике с помощью BOOST, как вы проверяете внешнюю планарность? намеки?

Answer 1

Возможно, уже слишком поздно, чтобы ответить, но я надеюсь, что это все равно поможет вам или кому-то еще, наткнувшись на этот вопрос.

На сегодняшний день в Boost до сих пор не реализован алгоритм тестирования внешней планарности, но на самом деле довольно просто проверить внешнюю планарность с помощью проверок плоскостности Boost.

Согласно статье Манфреда Вигерса " Распознавание внешнепланарных графов в линейном времени":

граф G является внешнепланарным тогда и только тогда, когда K₁ + G (новая вершина соединяется со всеми вершинами G) является плоской.

Таким образом, вам нужно добавить в граф дополнительную вершину с ребрами, соединяющими ее со всеми вершинами исходного графа, а затем проверить, является ли новый граф плоским. Если это так, то исходный граф является внешнепланарным.

Также отметим, что каждый внешний планарный граф с n вершинами имеет менее 2n- 3 ребер. Добавление этой проверки количества ребер может быстро отфильтровать многие явно не внешние планарные графы.