|
Наиболее известный критерий планарности графов формулируется в теореме Понтрягина-Куратовского: граф можно вложить в плоскость тогда и только тогда,
когда у него нет подграфов, гомеоморфных полному графу K5 или полному двудольному графу K3,3. Крестовым графом называется 4-валентный граф, в вершинах
которого задана крестовая структура, то есть указано разбиение примыкающих к вершине ребер на пары противоположных. В. А. Васильев выдвинул в качестве
гипотезы следующий критерий планарности крестовых графов: у крестового графа имеется вложение его в плоскость, сохраняющее крестовую структуру,
тогда и только тогда, когда граф не содержит пары циклов, имеющих единственную точку транверсального пересечения. Гипотеза Васильева была доказана
В. О. Мантуровым с использованием теории d-диаграмм.
В докладе мы приведем доказательство гипотезы Васильева, опирающееся на теорему Понтрягина-Куратовского, и обсудим связь этих двух критериев планарности
между собой, а также с другими критериями.
|
