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