Критерий планарности Уитни

Критерий планарности Уитни — это матроидное описание планарных графов. Критерий носит имя Хасслера Уитни^[1]. Критерий утверждает, что граф G планарен тогда и только тогда, когда его графовый матроид^[англ.] является также кографовым (то есть является двойственным матроидом^[англ.] другого графового матроида).

Планарный граф и двойственный ему. Любой цикл в голубом графе является минимальным сечением красного графа и наоборот, так что эти два графа алгебраически двойственны и имеют двойственные графовые матроиды.

В терминах чисто теории графов этот критерий можно сформулировать следующим образом: должен существовать другой (двойственный) граф G'=(V',E') и биективное соответствие между рёбрами E' и рёбрами E исходного графа G, такое, что подмножество T рёбер E образует остовное дерево графа G тогда и только тогда, когда рёбра, соответствующие дополнению множества E-T образуют остовное дерево графа G'.

Существуют и другие критерии планарности, например, теорема Понтрягина — Куратовского.

Алгебраическая двойственность

Эквивалентная форма критерия Уитни гласит, что граф G планарен тогда и только тогда, когда он имеет двойственный граф, графовый матроид которого двойственен графовому матроиду графа G. Граф, графовый матроид которого двойственен графовому матроида графа G, известен как алгебраически двойственный граф для графа G. Тогда критерий планарности Уитни можно перефразировать следующим образом: граф планарен тогда и только тогда, когда у него есть алгебраически двойственный граф.

Топологическая двойственность

Если граф вложен в топологическую поверхность, такую как плоскость, таким образом, что любая грань при вложении является топологическим диском, тогда двойственный граф вложения определяется как граф (в некоторых случаях — мультиграф) H, который имеет вершину для каждой грани вложения и ребро для каждой пары смежных граней. Согласно критерию Уитни следующие условия эквивалентны:

• Поверхность, на которой существует вложение, топологически эквивалентна плоскости, сфере или проколотой плоскости
• Граф H алгебраически двойственен G
• Любой простой цикл в G соответствует минимальному сечению в графе H, и наоборот
• Любой простой цикл в H соответствует минимальному сечению в графе G, и наоборот
• Любое остовное дерево в G соответствует дополнению остовного дерева в графе H, и наоборот^[2].

Можно определить двойственные графы графа, вложенного в неплоские поверхности, такие как тор, но такие двойственные графы, в общем случае, не имеют соответствия с сечениями, циклами и остовными деревьями, которое требует критерий Уитни.