Граф укладених трикутників із n вершинами — це планарний граф, утворений послідовністю n/3 трикутників, відповідні пари вершин яких з'єднано ребрами. Його можна утворити також геометрично, склеївши разом трикутних призм їхніми трикутними гранями. Цей граф і тісно пов'язані графи часто використовують у галузі візуалізації графів для доведення нижніх меж потрібної площі за різних стилів малювання.
Поліедральне подання
Граф укладених трикутників із двома трикутниками є графом трикутної призми, а граф укладених трикутників із трьома трикутниками — це граф [en]. Загальніше, оскільки графи вбудованих трикутників планарні і вершинно 3-зв'язні, з теореми Штайніца випливає, що їх можна подати як опуклі многогранники.
Альтернативне геометричне подання цих графів можна задати, склеївши трикутні призм трикутними гранями. Число вкладених трикутників на одиницю більше від числа склеєних призм. Однак, за використання прямокутних призм, після їх склеювання суміжні прямокутні грані виявляються компланарними, так що отримане тіло не є строго опуклим.
Нижні межі площі для малюнків графів
Назву «граф укладених трикутників» запропонували Долев, Лейтон і Трікі, які використали її, щоб показати, що малюнок планарного графа з n вершинами на цілочисельній ґратці (з ребрами у вигляді відрізків) може вимагати обмежувального прямокутника розміру щонайменше . У такому малюнку не суттєво, яку грань вибрано як зовнішнє ребро, деяка підпослідовність щонайменше з n/6 трикутників має бути намальована вкладеними один в одного і в цій частині малюнка кожен трикутник має використовувати на два рядки і на два стовпці більше, ніж наступний внутрішній трикутник. Якщо зовнішня грань не вибирається під час виконання алгоритму малювання, а задається, ті ж доводи показують, що необхідний обмежувальний прямокутник розміру і малюнок з такими розмірами існує.
Для малюнків, у яких зовнішню грань можна вибирати вільно, нижня межа площі Долева, Лейтона і Трікі може не бути жорсткою. Фраті і Патрігнані показали, що цей граф і будь-який граф, утворений додаванням діагоналей до його чотирикутників, можна намалювати в прямокутнику розміром . Якщо ніяких додаткових діагоналей не додано, граф укладених трикутників можна намалювати навіть із меншою площею, приблизно , як на малюнку. Закриття проміжку між верхньою межею і нижньою межею площі максимального планарного доповнення вкладеного трикутного графа залишається відкритою проблемою.
Яка площа мінімального обмежувального прямокутника при малюванні вкладеного трикутного графа на ґратці або його максимального планарного поповнення?
Варіанти вкладених трикутних графів використовувалися для багатьох інших побудов нижніх меж при малюванні графів, наприклад за площею прямокутного подання (коли вершини подано прямокутниками, а ребра малюються як ламані з паралельними до осей ланками), площі малюнків з перпендикулярними перетинами або відносної площі планарного подання порівняно з непланарним.
Примітки
- Frati, Patrignani, 2008.
- Dolev, Leighton, Trickey, 1984.
- Dolev, Leighton, Trickey, 1984, с. 147–161.
- Frati, Patrignani, 2008, с. 339–344.
- Fößmeier, Kant, Kaufmann, 1997, с. 155–168.
- Didimo, Liotta, 2013, с. 167–184.
- van Kreveld, 2011, с. 371–376.
Література
- Danny Dolev, F. Thomson Leighton, Howard Trickey. Planar embedding of planar graphs // Advances in Computing Research. — 1984. — Т. 2. — С. 147–161. з джерела 20 січня 2022. Процитовано 24 квітня 2022.
- 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. — () — DOI:
- 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:
- 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:
- 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:
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Graf ukladenih trikutnikiv iz n vershinami ce planarnij graf utvorenij poslidovnistyu n 3 trikutnikiv vidpovidni pari vershin yakih z yednano rebrami Jogo mozhna utvoriti takozh geometrichno skleyivshi razom n 3 1 displaystyle tfrac n 3 1 trikutnih prizm yihnimi trikutnimi granyami Cej graf i tisno pov yazani grafi chasto vikoristovuyut u galuzi vizualizaciyi grafiv dlya dovedennya nizhnih mezh potribnoyi ploshi za riznih stiliv malyuvannya Vkladeni trikutniki z 18 vershinamiPoliedralne podannya en Graf ukladenih trikutnikiv iz dvoma trikutnikami ye grafom trikutnoyi prizmi a graf ukladenih trikutnikiv iz troma trikutnikami ce graf en Zagalnishe oskilki grafi vbudovanih trikutnikiv planarni i vershinno 3 zv yazni z teoremi Shtajnica viplivaye sho yih mozhna podati yak opukli mnogogranniki Alternativne geometrichne podannya cih grafiv mozhna zadati skleyivshi trikutni prizm trikutnimi granyami Chislo vkladenih trikutnikiv na odinicyu bilshe vid chisla skleyenih prizm Odnak za vikoristannya pryamokutnih prizm pislya yih skleyuvannya sumizhni pryamokutni grani viyavlyayutsya komplanarnimi tak sho otrimane tilo ne ye strogo opuklim Nizhni mezhi ploshi dlya malyunkiv grafivDiv takozh Plosha vizualizaciya grafiv Malyunok grafa vkladenih trikutnikiv na gratci Ce podannya vikoristovuye menshu ploshu nizh podannya Frati ta Patrignani ale na vidminu vid nogo ne uzagalnyuyetsya do maksimalnogo planarnogo supergrafa vkladenih trikutnikiv Nazvu graf ukladenih trikutnikiv zaproponuvali Dolev Lejton i Triki yaki vikoristali yiyi shob pokazati sho malyunok planarnogo grafa z n vershinami na cilochiselnij gratci z rebrami u viglyadi vidrizkiv mozhe vimagati obmezhuvalnogo pryamokutnika rozmiru shonajmenshe n 3 n 3 displaystyle tfrac n 3 times tfrac n 3 U takomu malyunku ne suttyevo yaku gran vibrano yak zovnishnye rebro deyaka pidposlidovnist shonajmenshe z n 6 trikutnikiv maye buti namalovana vkladenimi odin v odnogo i v cij chastini malyunka kozhen trikutnik maye vikoristovuvati na dva ryadki i na dva stovpci bilshe nizh nastupnij vnutrishnij trikutnik Yaksho zovnishnya gran ne vibirayetsya pid chas vikonannya algoritmu malyuvannya a zadayetsya ti zh dovodi pokazuyut sho neobhidnij obmezhuvalnij pryamokutnik rozmiru 2 n 3 2 n 3 displaystyle tfrac 2n 3 times tfrac 2n 3 i malyunok z takimi rozmirami isnuye Dlya malyunkiv u yakih zovnishnyu gran mozhna vibirati vilno nizhnya mezha ploshi Doleva Lejtona i Triki mozhe ne buti zhorstkoyu Frati i Patrignani pokazali sho cej graf i bud yakij graf utvorenij dodavannyam diagonalej do jogo chotirikutnikiv mozhna namalyuvati v pryamokutniku rozmirom n 3 2 n 3 displaystyle tfrac n 3 times tfrac 2n 3 Yaksho niyakih dodatkovih diagonalej ne dodano graf ukladenih trikutnikiv mozhna namalyuvati navit iz menshoyu plosheyu priblizno n 3 n 2 displaystyle tfrac n 3 times tfrac n 2 yak na malyunku Zakrittya promizhku mizh verhnoyu mezheyu 2 n 2 9 displaystyle tfrac 2n 2 9 i nizhnoyu mezheyu n 2 9 displaystyle tfrac n 2 9 ploshi maksimalnogo planarnogo dopovnennya vkladenogo trikutnogo grafa zalishayetsya vidkritoyu problemoyu Nerozv yazana problema matematiki Yaka plosha minimalnogo obmezhuvalnogo pryamokutnika pri malyuvanni vkladenogo trikutnogo grafa na gratci abo jogo maksimalnogo planarnogo popovnennya Varianti vkladenih trikutnih grafiv vikoristovuvalisya dlya bagatoh inshih pobudov nizhnih mezh pri malyuvanni grafiv napriklad za plosheyu pryamokutnogo podannya koli vershini podano pryamokutnikami a rebra malyuyutsya yak lamani z paralelnimi do osej lankami ploshi malyunkiv z perpendikulyarnimi peretinami abo vidnosnoyi ploshi planarnogo podannya porivnyano z neplanarnim PrimitkiFrati Patrignani 2008 Dolev Leighton Trickey 1984 Dolev Leighton Trickey 1984 s 147 161 Frati Patrignani 2008 s 339 344 Fossmeier Kant Kaufmann 1997 s 155 168 Didimo Liotta 2013 s 167 184 van Kreveld 2011 s 371 376 LiteraturaDanny Dolev F Thomson Leighton Howard Trickey Planar embedding of planar graphs Advances in Computing Research 1984 T 2 S 147 161 z dzherela 20 sichnya 2022 Procitovano 24 kvitnya 2022 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 T 4875 S 339 344 DOI 10 1007 978 3 540 77537 9 33 Ulrich Fossmeier 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 T 1190 S 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 Janos Pach Springer 2013 S 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 T 6502 S 371 376 Lecture Notes in Computer Science DOI 10 1007 978 3 642 18469 7 34