Как сертифицировать плоское вложение?

Question

Я собираюсь реализовать алгоритм для вычисления плоского вложения.

Я начал проверять свои результаты, запустив набор графиков (графы Рима) и сравнив свои результаты с результатами другой реализации (yfiles). Тем не менее, я могу только проверить, равен ли плоский / не плоский ответ, потому что для данного плоского графа может существовать много разных вложений.

Как я могу проверить, что вычисленное мной вложение (упорядочение в списках смежности) является правильным плоским вложением?

Я уже обнаружил некоторые случаи, когда я, возможно, получаю неправильное вложение. Для неудачных графиков обычно рисование вложений вручную становится сложным. Я обнаружил, что в документах надбавки утверждается, что для любого графа можно составить чертеж графа в плоскости, который удостоверяет, что граф является плоским, а сертификат плоскостности легко проверить. Но я также не уверен, смогу ли я / как создать такой чертеж безошибочным алгоритмическим способом только из упорядоченных списков смежности.

(Кстати, вот мой код)

Answer 1

Самый простой способ, который я знаю, - это вычислить произвольное остовное дерево, а затем убедиться, что у оставшихся ребер нет циклов в двойственном графе. Если dnext(e) отображает половину e с головой v на следующую половину в направлении против часовой стрелки с головой v, а sym (e) - это половина, противоположная e, то rprev (e) = sym (dnext) (e)) является следующей половиной по часовой стрелке с той же правой гранью. Я реализовал этот подход в Algorithm.java моего проекта: http://www.davideisenstat.com/trickle/

В качестве альтернативы вы можете использовать характеристику Эйлера. Пометьте вершины (= циклы перестановки dnext) и грани (= циклы перестановки rprev) и определите, сколько существует связанных компонентов. Убедитесь, что (V - C) + (F - C) = E.