Вкладення Татта

Вкладення Татта (барицентричне вкладення) простого 3-вершинно-зв'язного планарного графа — вкладення без перетинів із ребрами у вигляді відрізків з додатковими властивостями, що межею зовнішньої грані є опуклий многокутник і кожна внутрішня вершина є геометричним центром сусідів. Якщо зовнішній многокутник фіксований, ця умова на внутрішні вершини визначає їх положення однозначно як розв'язок системи лінійних рівнянь. Розв'язування рівнянь дає планарне вкладення. Теорема Татта «про гумове вкладення» стверджує, що в єдиному розв'язку ніколи немає перетинів ребер і, строгіше, що будь-яка грань отриманого планарного вкладення опукла. Вкладення називають «гумовим», оскільки таке вкладення можна знайти як рівноважне положення системи пружин або гумових ременів, що представляють ребра графа.

Приклад

Вкладення Татта графа куба. Зовнішні чотири вершини фіксовані в кутах одиничного квадрата, а решта вершин є геометричними центрами сусідніх вершин.

Нехай ${\displaystyle G}$ — граф куба. Зафіксуємо (вибравши одну з чотирикутних граней як зовнішню грань) чотири вершини зовнішньої грані в кутах одиничного квадрата, координати x і y якого є комбінаціями нулів і одиниць. Чотири інші вершини тоді розташовуються в чотирьох точках, координати x і y яких є комбінаціями 1/3 і 2/3, як показано на малюнку. Результат — вкладення Татта. Для кожної внутрішньої вершини ${\displaystyle v}$ цього вкладення сусідні три вершини мають три значення координат (як x, так і y), одне з яких дорівнює координаті ${\displaystyle v}$, одне менше, а інше більше на 1/3. У середньому отримуємо значення координати самої точки ${\displaystyle v}$.

Система лінійних рівнянь

Умова, що вершина v має середнє значення координат сусідів, можна виразити у вигляді двох лінійних рівнянь: одне — для координати точки x, інше — для координати y. Для графа з n вершинами, h із яких зафіксовано у вершинах зовнішньої грані, є два рівняння та два невідомих (координати) для кожної внутрішньої вершини. Таким чином, отримуємо систему лінійних рівнянь з 2(n − h) рівняннями з 2(n − h) невідомими, розв'язком якої буде вкладення Татта. Як показав Татт, для 3-вершинно-зв'язних планарних графів ця система не вироджена. Тому система матиме єдиний розв'язок і (з фіксованою зовнішньою гранню) граф буде єдиним вкладенням Татта. Це вкладення можна знайти за поліноміальний час, розв'язавши систему рівнянь, наприклад, за допомогою послідовного виключення змінних.

Подання многогранників

За теоремою Штайніца 3-зв'язні планарні графи, для яких застосовується теорема Татта «про гумове вкладення», збігаються з поліедральними графами, — графами, утвореними вершинами та ребрами опуклого многогранника. За методом Максвелла — Кремони двовимірне вкладення планарного графа утворює проєкцію тривимірного опуклого многогранника тоді й лише тоді, коли вкладення має рівноважну напругу, розподіл сил для кожного ребра (в обох кінцях ребер у протилежних напрямках, паралельних ребрам), так що сили в кожній вершині зрівноважуються. Для вкладення Татта розподіл сил кожного ребра пропорційно довжині ребра (подібно до гумки) врівноважує сили в усіх внутрішніх точках, але не у вершинах зовнішнього многокутника. Якщо зовнішній многокутник є трикутником, можна на трьох зовнішніх ребрах призначити відштовхувальні сили, які зрівноважать сили у вершинах зовнішнього трикутника. Таким чином, вкладення Татта можна використати для пошуку діаграм Шлегеля будь-якого опуклого многогранника. Для будь-якого 3-зв'язного планарного графа G або сам граф G, або його двоїстий має трикутник, так що отримуємо многогранне подання графа G або його двоїстого. Якщо двоїстий граф має трикутну грань, полярне спряження дає многогранне подання самого графа G.

Узагальнення

Гортлер, Готсман і Терстон довели результати, аналогічні теоремі Татта «про гумове вкладення», для вкладень графів у тор.

Чилакамаррі, Дін і Літман досліджували тривимірне вкладення графів чотиривимірних многогранників, утворене тим самим методом, що й у методі вкладення Татта — вибираємо одну зовнішню фасету многогранника як зовнішню грань тривимірного вкладення і фіксуємо положення вершин у тривимірному просторі. Інші вершини многогранника можна рухати, а ребра замінимо пружинами (або гумовими шнурами). Тепер знайдемо конфігурацію системи пружин із найменшою енергією. Як вони показали, система рівнянь, отримана в такий спосіб, також буде невиродженою, але залишається незрозумілим, за яких умов цей метод дасть вкладення, в якому всі грані многогранника будуть опуклими.

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

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

Граф k-вершинно-зв'язний (але не обов'язково планарний) тоді й лише тоді, коли він має вкладення в (k−1)-вимірний простір, у якому будь-який набір з k вершин розташовується у вершинах симплекса, а для будь-якої з решти вершин v опукла оболонка її сусідів має повну розмірність і v розташовується всередині цієї оболонки. Якщо таке вкладення існує, його можна знайти, зафіксувавши положення k вершин і розв'язавши систему рівнянь. Розв'язок розміщує кожну вершину в місце, що є середнім положень сусідів, так само, як за планарного вкладення Татта.

У методі скінченних елементів при побудові загальним методом постобробки отриманої сітки для покращення якості є ^[en], що особливо популярно для чотирикутних сіток, для яких інші методи, такі як алгоритм Ллойда для згладжування трикутних сіток, менш застосовні. У цьому методі кожна вершина рухається в напрямку середнього значення положень сусідів, але цей рух здійснюється за малу кількість ітерацій, щоб уникнути значного спотворення розмірів елементів, або (в разі неопуклої ділянки сітки) отримання сплутаних непланарних сіток.

Силові методи вкладання графів залишаються популярними методами візуалізації графів, але в них зазвичай використовують складніші системи сил, комбінуючи сили притягання ребер графа (як у вкладенні Татта) зі силами відштовхування між довільними парами вершин. Ці додаткові сили можуть дати системі багато локальних стійких конфігурацій, а не одну глобальну, як у вкладенні Татта.

Примітки

1. Tutte, 1963, с. 743–767.
2. Tutte, 1963.
3. Rote, 2012, с. 238–241.
4. Gortler, Gotsman, Thurston, 2006.
5. Gortler, Gotsman, Thurston, 2006, с. 83–112.
6. Chilakamarri, Dean, Littman, 1995.
7. Chilakamarri, Dean, Littman, 1995, с. 129–140.
8. Про зв'язок між теоремами Татта і Фарі та історію перевідкриття теореми Фарі див. книгу Фелснера (Felsner, 2012).
9. Linial, Lovász, Wigderson, 1988, с. 91–102.
10. Herrmann, 1976, с. 749–907.
11. Kobourov, 2012.

Література

• Steven J. Gortler, Craig Gotsman, Dylan Thurston. Discrete one-forms on meshes and applications to 3D mesh parameterization // Computer Aided Geometric Design. — 2006. — Т. 23, вип. 2. — С. 83–112. — DOI:10.1016/j.cagd.2005.05.002.
• Günter Rote. Graph Drawing: 19th International Symposium, GD 2011, Eindhoven, The Netherlands, September 21–23, 2011, Revised Selected Papers. — Springer, 2012. — Т. 7034. — С. 238–241. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-25878-7_23.
• Kiran Chilakamarri, Nathaniel Dean, Michael Littman. Three-dimensional Tutte embedding // Congressus Numerantium, Proceedings of the Twenty-sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1995). — 1995. — Т. 107. — С. 129–140.
• Stefan Felsner. Geometric Graphs and Arrangements: Some Chapters from Combinatorial Geometry. — Springer, 2012. — С. 37. — (Advanced Lectures in Mathematics) — .
• N. Linial, L. Lovász, A. Wigderson. Rubber bands, convex embeddings and graph connectivity // . — 1988. — Т. 8, вип. 1. — С. 91–102. — DOI:10.1007/BF02122557.
• Leonard R. Herrmann. Laplacian-isoparametric grid generation scheme // Journal of the Engineering Mechanics Division. — 1976. — Т. 102, вип. 5. — С. 749–907.
• W. T. Tutte. How to draw a graph // Proceedings of the London Mathematical Society. — 1963. — Т. 13. — С. 743–767. — DOI:10.1112/plms/s3-13.1.743.
• Stephen G. Kobourov. Spring Embedders and Force-Directed Graph Drawing Algorithms. — 2012. — arXiv:1201.3011.