Критерій планарності Вітні — це матроїдний опис планарних графів. Критерій названо іменем . Критерій стверджує, що граф планарний тоді й лише тоді, коли його є також кографовим (тобто є іншого графового матроїда).
У термінах чисто теорії графів цей критерій можна сформулювати так:
Існують і інші критерії планарності, наприклад, теорема Понтрягіна — Куратовського.
Алгебрична двоїстість Еквівалентна форма критерію Вітні:
Граф, графовий матроїд якого двоїстий графовому матроїду графа , знаний як алгебрично двоїстий граф для графа . Тоді критерій планарності Вітні можна перефразувати так:
Топологічна двоїстість Якщо граф укладено в топологічну поверхню, таку як площина, так, що будь-яка грань при вкладенні є топологічним диском, то двоїстий граф вкладення визначається як граф (у деяких випадках — мультиграф) , який має вершину для кожної грані вкладення і ребро для кожної пари суміжних граней. Згідно з критерієм Вітні такі умови еквівалентні:
поверхня, на якій існує вкладення, топологічно еквівалентна площині, сфері або проколотій площині; граф алгебрично двоїстий ; будь-який простий цикл у відповідає мінімальному перерізу в графі , і навпаки; будь-який простий цикл у відповідає мінімальному перерізу в графі , і навпаки; будь-яке кістякове дерево в відповідає доповненню кістякового дерева в графі , і навпаки.
Можна визначити двоїсті графи графа, вкладеного в неплоскі поверхні, такі як тор, але такі двоїсті графи, в загальному випадку, не мають відповідності з розрізами, циклами і кістяковими деревами, яку вимагає критерій Вітні.
Див. також Перевірка планарності
Примітки
Література
. Див., зокрема, стор. 5–6 розділу 2.5 «Bon-matroid of a graph», стор. 19–20 розділу 5.6 «Graphic and co-graphic matroids» і стор. 38–47 розділу 9 «Graphic matroids»