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

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

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

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

Шаблон:Не перекладено

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

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

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

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

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

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

Література

• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга