Граф укладених трикутників

Вкладені трикутники з 18 вершинами

Граф укладених трикутників із n вершинами — це планарний граф, утворений послідовністю n/3 трикутників, відповідні пари вершин яких з'єднано ребрами. Його можна утворити також геометрично, склеївши разом ${\tfrac {n}{3}}-1$ трикутних призм їхніми трикутними гранями. Цей граф і тісно пов'язані графи часто використовують у галузі візуалізації графів для доведення нижніх меж потрібної площі за різних стилів малювання.

Поліедральне подання

Двозрізана біпіраміда

Граф укладених трикутників із двома трикутниками є графом трикутної призми, а граф укладених трикутників із трьома трикутниками — це граф двозрізаної біпіраміди. Загальніше, оскільки графи вбудованих трикутників планарні і вершинно 3-зв'язні, з теореми Штайніца випливає, що їх можна подати як опуклі многогранники.

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

Нижні межі площі для малюнків графів

Малюнок графа вкладених трикутників на ґратці. Це подання використовує меншу площу, ніж подання Фраті та Патрігнані, але, на відміну від нього, не узагальнюється до максимального планарного суперграфа вкладених трикутників.

Назву «граф укладених трикутників» запропонували Долев, Лейтон і Трікі, які використали її, щоб показати, що малюнок планарного графа з n вершинами на цілочисельній ґратці (з ребрами у вигляді відрізків) може вимагати обмежувального прямокутника розміру щонайменше ${\tfrac {n}{3}}\times {\tfrac {n}{3}}$. У такому малюнку не суттєво, яку грань вибрано як зовнішнє ребро, деяка підпослідовність щонайменше з n/6 трикутників має бути намальована вкладеними один в одного і в цій частині малюнка кожен трикутник має використовувати на два рядки і на два стовпці більше, ніж наступний внутрішній трикутник. Якщо зовнішня грань не вибирається під час виконання алгоритму малювання, а задається, ті ж доводи показують, що необхідний обмежувальний прямокутник розміру ${\tfrac {2n}{3}}\times {\tfrac {2n}{3}}$ і малюнок з такими розмірами існує.

Для малюнків, у яких зовнішню грань можна вибирати вільно, нижня межа площі Долева, Лейтона і Трікі може не бути жорсткою. Фраті і Патрігнані показали, що цей граф і будь-який граф, утворений додаванням діагоналей до його чотирикутників, можна намалювати в прямокутнику розміром ${\tfrac {n}{3}}\times {\tfrac {2n}{3}}$. Якщо ніяких додаткових діагоналей не додано, граф укладених трикутників можна намалювати навіть із меншою площею, приблизно ${\tfrac {n}{3}}\times {\tfrac {n}{2}}$, як на малюнку. Закриття проміжку між верхньою межею ${\tfrac {2n^{2}}{9}}$ і нижньою межею ${\tfrac {n^{2}}{9}}$ площі максимального планарного доповнення вкладеного трикутного графа залишається відкритою проблемою.

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

Яка площа мінімального обмежувального прямокутника при малюванні вкладеного трикутного графа на ґратці або його максимального планарного поповнення?

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

Література

• Danny Dolev, F. Thomson Leighton, Howard Trickey. Planar embedding of planar graphs // Advances in Computing Research. — 1984. — Т. 2 (29 травня). — С. 147–161.
• Fabrizio Frati, Maurizio Patrignani. A note on minimum-area straight-line drawings of planar graphs // Graph Drawing: 15th International Symposium, GD 2007, Sydney, Australia, September 24-26, 2007, Revised Papers. — Berlin : Springer, 2008. — Т. 4875. — С. 339–344. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-540-77537-9_33.
• Ulrich Fößmeier, Goos Kant, Michael Kaufmann. 2-visibility drawings of planar graphs // Graph Drawing: Symposium on Graph Drawing, GD '96 Berkeley, California, USA, September 18–20, 1996, Proceedings. — 1997. — Т. 1190. — С. 155–168. — (Lecture Notes in Computer Science) — DOI:10.1007/3-540-62495-3_45.
• Walter Didimo, Giuseppe Liotta. The crossing-angle resolution in graph drawing // Thirty Essays on Geometric Graph Theory / János Pach. — Springer, 2013. — С. 167–184. — DOI:10.1007/978-1-4614-0110-0_10.
• Marc van Kreveld. The quality ratio of RAC drawings and planar drawings of planar graphs // Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers / Ulrik Brandes, Sabine Cornelsen. — 2011. — Т. 6502. — С. 371–376. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-18469-7_34.