Граф укладених трикутників із n вершинами — це планарний граф, утворений послідовністю n/3 трикутників, відповідні пари вершин яких з'єднано ребрами. Його можна утворити також геометрично, склеївши разом трикутних призм їхніми трикутними гранями. Цей граф і тісно пов'язані графи часто використовують у галузі візуалізації графів для доведення нижніх меж потрібної площі за різних стилів малювання.
Поліедральне подання
Граф укладених трикутників із двома трикутниками є графом трикутної призми, а граф укладених трикутників із трьома трикутниками — це граф . Загальніше, оскільки графи вбудованих трикутників планарні і вершинно 3-зв'язні, з теореми Штайніца випливає, що їх можна подати як опуклі многогранники.
Альтернативне геометричне подання цих графів можна задати, склеївши трикутні призм трикутними гранями. Число вкладених трикутників на одиницю більше від числа склеєних призм. Однак, за використання прямокутних призм, після їх склеювання суміжні прямокутні грані виявляються компланарними, так що отримане тіло не є строго опуклим.
Нижні межі площі для малюнків графів
Назву «граф укладених трикутників» запропонували Долев, Лейтон і Трікі, які використали її, щоб показати, що малюнок планарного графа з n вершинами на цілочисельній ґратці (з ребрами у вигляді відрізків) може вимагати обмежувального прямокутника розміру щонайменше . У такому малюнку не суттєво, яку грань вибрано як зовнішнє ребро, деяка підпослідовність щонайменше з n/6 трикутників має бути намальована вкладеними один в одного і в цій частині малюнка кожен трикутник має використовувати на два рядки і на два стовпці більше, ніж наступний внутрішній трикутник. Якщо зовнішня грань не вибирається під час виконання алгоритму малювання, а задається, ті ж доводи показують, що необхідний обмежувальний прямокутник розміру і малюнок з такими розмірами існує.
Для малюнків, у яких зовнішню грань можна вибирати вільно, нижня межа площі Долева, Лейтона і Трікі може не бути жорсткою. Фраті і Патрігнані показали, що цей граф і будь-який граф, утворений додаванням діагоналей до його чотирикутників, можна намалювати в прямокутнику розміром . Якщо ніяких додаткових діагоналей не додано, граф укладених трикутників можна намалювати навіть із меншою площею, приблизно , як на малюнку. Закриття проміжку між верхньою межею і нижньою межею площі максимального планарного доповнення вкладеного трикутного графа залишається відкритою проблемою.Варіанти вкладених трикутних графів використовувалися для багатьох інших побудов нижніх меж при малюванні графів, наприклад за площею прямокутного подання (коли вершини подано прямокутниками, а ребра малюються як ламані з паралельними до осей ланками), площі малюнків з перпендикулярними перетинами або відносної площі планарного подання порівняно з непланарним.
Примітки
Література