Теорема Шнайдера

Теорема Шнайдера — це опис планарного графа в термінах порядкової розмірності його частково упорядкованої множини інцидентності вершин. Теорему названо ім'ям Вальтера Шнайдера, який опублікував її доведення 1989 року.

Частково впорядкована множина інцидентних вершин $P(G)$ неорієнтованого графа $G$ з множиною вершин $V$ і множиною ребер $E$ — це частково впорядкована множина висоти 2, яка має $V\cup E$ як елементи. У цій частково впорядкованій множині є відношення порядку $x<y$ якщо $x$ є вершиною, $y$ є ребром і $x$ є одним із кінців $y$.

Порядкова розмірність частково впорядкованої множини — це найменша кількість повних порядків, перетин яких дає дану частково впорядковану множину. Таку множину порядків називають реалізатором частково впорядкованої множини. Теорема Шнайдера стверджує, що граф $G$ є планарним тоді й лише тоді, коли порядкова розмірність $P(G)$ не перевищує трьох.

Розширення

Теорему узагальнили Брайтвел і Троттер для отримання точної оцінки розмірності частково впорядкованих множин висоти три, утворених аналогічно з вершин ребер і граней опуклого многогранника, або, загальніше, вкладеного планарного графа. В обох випадках порядкова розмірність частково впорядкованої множини не перевищує чотирьох. Однак результат не можна узагальнити на багатовимірні опуклі многогранники, тому що існують чотиривимірні многогранники, решітки граней яких мають необмежену порядкову розмірність.

Для абстрактних симпліційних комплексів порядкова розмірність частково впорядкованої множини граней комплексу не перевищує 1 + d, де d — найменша розмірність евклідового простору, в якому комплекс має геометричну реалізацію.

Інші графи

Як зауважив Шнайдер, частково впорядкована множина інцидентності вершин графа $G$ має порядкову розмірність два тоді й лише тоді, коли граф є шляхом або підграфом шляху. Щоб частково впорядкована множина інцидентності вершин мала порядкову розмірність два, необхідно, щоб реалізатор складався з двох повних порядків, які (обмежені вершинами графа) обернені один до одного. Будь-які інші два порядки давали б перетин, який включає відношення порядку між двома вершинами, що неприпустимо для частково впорядкованої множини інцидентності вершин. Для цих двох порядків на вершинах ребро між двома сусідніми вершинами можна включити в порядок, розмістивши його безпосередньо за останнім з двох кінцевих вершин ребра^{[прояснити]}, але інші ребра включити не можна.

Якщо граф можна розфарбувати в чотири кольори, то його частково впорядкована множина інцидентності вершин має порядкову розмірність, що не перевищує 4 (Schnyder, 1989) .

Частково впорядкована множина інцидентності вершин повного графа з n вершинами має порядкову розмірність $\Theta (\log \log n)$.

Література

• Brightwell G., Trotter W. T. The order dimension of convex polytopes // SIAM Journal on Discrete Mathematics. — 1993. — Т. 6, вип. 2. — С. 230–245. — DOI:10.1137/0406018.
• Brightwell G., Trotter W. T. The order dimension of planar maps // SIAM Journal on Discrete Mathematics. — 1997. — Т. 10, вип. 4. — С. 515–528. — DOI:10.1137/S0895480192238561.
• Ossona de Mendez P. Geometric realization of simplicial complexes // Proc. Int. Symp. Graph Drawing (GD 1999) / Kratochvil J. — Springer-Verlag, 1999. — Т. 1731. — С. 323–332. — (Lecture Notes in Computer Science) — DOI:10.1007/3-540-46648-7_33.
• Ossona de Mendez P. Realization of posets // Journal of Graph Algorithms and Applications. — 2002. — Т. 6, вип. 1. — С. 149–153.
• Schnyder W. Planar graphs and poset dimension // Order. — 1989. — Т. 5. — С. 323–343. — DOI:10.1007/BF00353652.
• Spencer J. Minimal scrambling sets of simple orders // Acta Mathematica Academiae Scientiarum Hungaricae. — 1971. — Т. 22. — С. 349–353. — DOI:10.1007/bf01896428.