Описание тега planar-graph

В теории графов планарный граф - это граф, который можно вложить в плоскость, т. Е. Его можно нарисовать на плоскости таким образом, чтобы его ребра пересекались только в своих конечных точках. Другими словами, его можно нарисовать таким образом, чтобы никакие грани не пересекались.

Проверка того, является ли граф планарным или нет, называется тестированием планарности. Теорема Куратовского утверждает, что граф является плоским тогда и только тогда, когда он не содержит подграфа, который является подразделением K5 (полный граф на пяти вершинах) или K3,3 (граф полезности, полный двудольный граф на шести вершинах, трех из которых подключаются к каждому из трех других). Такой подграф называется подграфом Куратовского. Существует множество алгоритмов определения того, является ли определенный граф планарным, одним из самых известных является алгоритм Бойера-Мирволда в O(n) (где n - количество вершин).

Используйте этот тег, если у вас есть вопросы о реализациях тестирования планарности, библиотеках или проблемах с планарным графом в целом.