Проверка внешней диаграммы с использованием BOOST?

Question

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

Answer 1

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

До сих пор Boost по-прежнему не имеет алгоритма тестирования внешней плантации, но на самом деле довольно просто проверить внешнююпланарность с помощью проверок планальности Boost.

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

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