Теорема Фарі про розпрямлення графа

Теоре́ма Фа́рі — теоретико-графове твердження про можливість випрямити ребра будь-якого планарного графа. Іншими словами, дозвіл малювати ребра не у вигляді відрізків, а у вигляді кривих, не розширює класу планарних графів.

Названа на честь угорського математика Іштвана Фарі, хоча довели її незалежно Клаус Вагнер 1936 і Штайн 1951 року.

Формулювання:

будь-який простий планарний граф має плоске подання, в якому всі ребра зображено відрізками прямих.

Доведення

Крок індукції.

Один з способів доведення теореми Фарі — застосування математичної індукції. Нехай G — простий планарний граф із n вершинами. Ми можемо вважати граф максимальним планарним, за необхідності можна додати ребра в початковий граф G. Всі грані графа G в цьому випадку мають бути трикутниками, оскільки в будь-яку грань з більшим числом сторін можна додати ребро, не порушуючи планарності графа, що суперечить домовленості про максимальність графа. Виберемо деякі три вершини a, b, c, що утворюють трикутну грань графа G. Доведемо за індукцією за n, що існує комбінаторно ізоморфне інше вкладення з прямими ребрами графа G, в якому трикутник abc є зовнішньою гранню вкладення. (Комбінаторна ізоморфність означає, що вершини, ребра і грані нового малюнка можна зробити відповідними елементами старого малюнка і при цьому зберігаються всі відношення інцидентності між ребрами, вершинами і гранями, а не тільки між вершинами і ребрами.) База індукції тривіальна, коли a, b і c є єдиними вершинами в G (n=3).

За формулою Ейлера для планарних графів граф G має 3n − 6 ребер. Еквівалентно, якщо визначити дефіцит вершини v у графі G як 6 − deg(v), сума дефіцитів дорівнює12. Кожна вершина у графі G може мати дефіцит не більший від трьох, так що є щонайменше чотири вершини з додатним дефіцитом. Зокрема, ми можемо вибрати вершину v з не більше ніж п'ятьма сусідами, відмінну від a, b і c. Нехай G утворюється видаленням вершини v з графа G і тріангуляцією грані f, отриманої після видалення вершини v. За індукцією, граф G' має комбінаторно-ізоморфне вкладення з прямолінійними ребрами, в якому abc є зовнішньою гранню. Оскільки отримане вкладення G було комбінаторно ізоморфним G', видалення з нього ребер, доданих для отримання графа G', залишає грань f, яка тепер є многокутником P з не більше ніж п'ятьма сторонами. Для отримання малюнка G з комбінаторно-ізоморфним вкладенням із прямими ребрами, вершину v слід додати до многокутника і з'єднати відрізками з його вершинами. За теоремою галереї мистецтв всередині P існує точка, куди можна помістити вершину v, так що ребра, які з'єднують вершину v з вершинами многокутника P, не перетнуть інших ребер многокутника, що завершує доведення.

Крок індукції доведення проілюстровано праворуч.

Пов'язані результати

Де Фрейсікс, Пах і Полак показали, як знайти за лінійний час малюнок із прямолінійними ребрами на ґратці з розмірами, що лінійно залежать від розміру графа, даючи універсальну множину точок із квадратичними розмірами. Схожий метод використав Шнайдер для доведення покращених меж та характеристики планарності, де він ґрунтувався на частковому порядку інцидентності. Його робота наголошує на існуванні певного розбиття ребер максимального планарного графа на три дерева, які відомі як ліс Шнайдера.

Теорема Татта «про гумове укладання» стверджує, що будь-який тризв'язний планарний граф можна намалювати на площині без перетинів так, що його ребра будуть відрізками прямих і зовнішня грань буде опуклим многокутником. Назва відбиває той факт, що таке вкладення можна знайти як точку рівноваги системи пружин, які подають ребра графа.

Теорема Штайніца стверджує, що будь-який 3-зв'язний планарний граф можна подати як ребра опуклого многогранника в тривимірному просторі. Вкладення з прямими ребрами графа $G$ можна отримати як проєкцію такого многогранника на площину.

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

Нерозв'язана проблема математики

Чи існує для будь-якого планарного графа подання з прямими ребрами, в якому довжини всіх ребер є цілими числами?

Гайко Гарборт порушив питання, чи існує для будь-якого планарного графа подання з прямими ребрами, в якому всі довжини ребер є цілими числами. Питання, чи істинна гіпотеза Гарборта, залишається відкритим (Станом на 2014). Однак відомо, що вкладення з цілими прямими ребрами існує для кубічних графів.

Сакс порушив питання, чи має будь-який граф із незачепленим вкладенням у тривимірному евклідовому просторі незачеплене вкладення, в якому всі ребра подано відрізками за аналогією з теоремою Фарі для двовимірних вкладень.

Див. також

• Мінімізація зламів

Література

• István Fáry. On straight-line representation of planar graphs // Acta Sci. Math. (Szeged). — 1948. — Т. 11. — С. 229–233. — MR0026311.
• Gary Chartrand, Linda Lesniak, Ping Zhang. Graphs & Digraphs. — 5th. — CRC Press, 2010. — С. 259–260. — ISBN 9781439826270.
• Hubert de Fraysseix, János Pach, Richard Pollack. Small sets supporting Fary embeddings of planar graphs // Twentieth Annual ACM Symposium on Theory of Computing. — 1988. — С. 426–433. — ISBN 0-89791-264-0. — DOI:10.1145/62212.62254.
• Hubert de Fraysseix, János Pach, Richard Pollack. How to draw a planar graph on a grid // Combinatorica. — 1990. — Т. 10. — С. 41–51. — DOI:10.1007/BF02122694.
• Jim Geelen, Anjie Guo, David McKinnon. Straight line embeddings of cubic planar graphs with integer edge lengths // J. Graph Theory. — 2008. — Т. 58, вип. 3. — С. 270–274. — DOI:10.1002/jgt.20304.
• Harborth H., Kemnitz A., Moller M., Sussenbach A. Ganzzahlige planare Darstellungen der platonischen Korper // Elem. Math.. — 1987. — Т. 42. — С. 118–122.
• Kemnitz A., Harborth H. Plane integral drawings of planar graphs // Discrete Math.. — 2001. — Т. 236. — С. 191–195. — DOI:10.1016/S0012-365X(00)00442-8.
• Bojan Mohar, Carsten Thomassen. Graphs on Surfaces. — Johns Hopkins University Press, 2001. — С. roblem 2.8.15. — ISBN 0-8018-6689-8.
• Horst Sachs. On a spatial analogue of Kuratowski's theorem on planar graphs — An open problem // Graph Theory: Proceedings of a Conference held in Łagów, Poland, February 10–13, 1981. — Springer-Verlag, 1983. — Т. 1018. — С. 230–241. — (Lecture Notes in Mathematics) — ISBN 978-3-540-12687-4. — DOI:10.1007/BFb0071633.
• Walter Schnyder. Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA). — 1990. — С. 138–148.
• Stein S. K. Convex maps // Proceedings of the American Mathematical Society. — 1951. — Т. 2, вип. 3. — С. 464–466. — DOI:10.2307/2031777.
• Tutte W. T. How to draw a graph // Proceedings of the London Mathematical Society. — 1963. — Т. 13. — С. 743–767. — DOI:10.1112/plms/s3-13.1.743.
• Klaus Wagner. Bemerkungen zum Vierfarbenproblem // Jahresbericht der Deutschen Mathematiker-Vereinigung. — 1936. — Т. 46. — С. 26–32.