Реализация алгоритма тестирования планарности

Question

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

Есть ли какая-либо реализация, такая как Бойер-Мирволд или любая другая, доступная на C++ или Java, которая выполняет то, что я спрашиваю?

Answer 1

Реализация в Boost of Boyer-Myrvold довольно понятна и очень хорошо прокомментирована.

https://www.boost.org/doc/libs/1_67_0/boost/graph/planar_detail/boyer_myrvold_impl.hpp

Однако я бы не стал читать код без предварительного чтения оригинальной статьи.

Answer 2

В этом тезисе есть подробное описание метода сложения путей при тестировании на плоскость (как математическая теория, так и алгоритмическая реализация).

Полный исходный код Java также содержится в приложениях, поддерживающих:

• Тестирование на плоскостность;
• Генерация плоского вложения; а также
• Для циклического генерирования всех возможных плоских вложений двусвязного графа (за линейное время, пропорциональное количеству ребер и количеству вложений для генерации всех вложений).