Теорема Шнайдера
Теорема Шнайдера — це опис планарного графа в термінах порядкової розмірності[en] його частково упорядкованої множини інцидентності вершин[en]. Теорему названо ім'ям Вальтера Шнайдера, який опублікував її доведення 1989 року.
Частково впорядкована множина інцидентних вершин неорієнтованого графа з множиною вершин і множиною ребер — це частково впорядкована множина висоти 2, яка має як елементи. У цій частково впорядкованій множині є відношення порядку якщо є вершиною, є ребром і є одним із кінців .
Порядкова розмірність частково впорядкованої множини — це найменша кількість повних порядків, перетин яких дає дану частково впорядковану множину. Таку множину порядків називають реалізатором частково впорядкованої множини. Теорема Шнайдера стверджує, що граф є планарним тоді й лише тоді, коли порядкова розмірність не перевищує трьох.
Теорему узагальнили Брайтвел і Троттер[1][2] для отримання точної оцінки розмірності частково впорядкованих множин висоти три, утворених аналогічно з вершин ребер і граней опуклого многогранника, або, загальніше, вкладеного планарного графа. В обох випадках порядкова розмірність частково впорядкованої множини не перевищує чотирьох. Однак результат не можна узагальнити на багатовимірні опуклі многогранники, тому що існують чотиривимірні многогранники, решітки граней[en] яких мають необмежену порядкову розмірність.
Для абстрактних симпліційних комплексів порядкова розмірність частково впорядкованої множини граней комплексу не перевищує 1 + d, де d — найменша розмірність евклідового простору, в якому комплекс має геометричну реалізацію[3][4].
Як зауважив Шнайдер, частково впорядкована множина інцидентності вершин графа має порядкову розмірність два тоді й лише тоді, коли граф є шляхом або підграфом шляху. Щоб частково впорядкована множина інцидентності вершин мала порядкову розмірність два, необхідно, щоб реалізатор складався з двох повних порядків, які (обмежені вершинами графа) обернені один до одного. Будь-які інші два порядки давали б перетин, який включає відношення порядку між двома вершинами, що неприпустимо для частково впорядкованої множини інцидентності вершин. Для цих двох порядків на вершинах ребро між двома сусідніми вершинами можна включити в порядок, розмістивши його безпосередньо за останнім з двох кінцевих вершин ребра[прояснити], але інші ребра включити не можна.
Якщо граф можна розфарбувати в чотири кольори, то його частково впорядкована множина інцидентності вершин має порядкову розмірність, що не перевищує 4 (Schnyder, 1989) .
Частково впорядкована множина інцидентності вершин повного графа з n вершинами має порядкову розмірність [5].
- Brightwell G., Trotter W. T. The order dimension of convex polytopes // SIAM Journal on Discrete Mathematics. — 1993. — Т. 6, вип. 2. — С. 230–245. — DOI: .
- Brightwell G., Trotter W. T. The order dimension of planar maps // SIAM Journal on Discrete Mathematics. — 1997. — Т. 10, вип. 4. — С. 515–528. — DOI: .
- 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:
- 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[en]. — 1989. — Т. 5. — С. 323–343. — DOI: .
- Spencer J. Minimal scrambling sets of simple orders // Acta Mathematica Academiae Scientiarum Hungaricae. — 1971. — Т. 22. — С. 349–353. — DOI: .