Число черг графа — це інваріант графа, визначений аналогічно стековому числу (товщині книги) і використовує впорядкування FIFO (перший увійшов, перший вийшов, черга) замість упорядкування LIFO (останнім увійшов, першим вийшов, стек).
Визначення
Подання заданого графа як черг (макет черг) визначається повним упорядкуванням вершин графа разом із розкладанням (ребер) графа на кілька «черг». Потрібно, щоби множини ребер кожної з черг не мали вкладеності за порядком вершин у тому сенсі, що якщо і — два ребра в одній черзі, то не повинно бути . Число черг графа — це найменше число черг подання графа у вигляді черг.
Використовуючи макет черг графа, можна перебрати ребра окремої черги, застосовуючи стандартну структуру черг шляхом перебору вершин у заданому порядку і коли досягаємо вершини, вибираємо всі ребра, для яких вершина є другою вершиною дуги і заносимо в чергу дуги, для яких вершина є першою. Умова відсутності вкладеності забезпечує, що з досягненням вершини все ребра, що мають цю вершину як кінцеву, перебувають у черзі і готові до вибирання. Розклад графа на черги з описаними властивостями можна вважати альтернативним визначенням. Інше еквівалентне визначення макета черг використовує поняття вкладення заданого графа в циліндр із вершинами, розташованими на прямій, що лежить на поверхні циліндра, а кожне ребро огинає циліндр. Ребра, включені в одну чергу, не повинні перетинатися, але перетини ребер різних черг дозволено.
Макет черг увели Гіт і Розенберг за аналогією з попередньою роботою про книжкові вкладення графів, які визначаються в той самий спосіб з використанням стеків замість черг. Як вони зазначили, ці макети також пов'язані з ранніми роботами про сортування перестановок із використанням паралельних черг і до створення пов'язане з розробкою інтегральних схем та управлінням зв'язками в [en].
Класи графів з обмеженою кількістю черг
Будь-яке дерево має число черг, що дорівнює 1 з упорядкуванням вершин, заданим пошуком у ширину. У псевдолісів і решіток число черг також дорівнює 1. Число черг зовніпланарних графів не перевищує 2. Сонячний 3-граф (трикутник, кожне ребро якого замінено трикутником) є прикладом зовніпланарного графа, число черг якого дорівнює 2. Число черг паралельно-послідовного графа не перевищує 3.
Число черг двійкових графів де Брейна дорівнює 2. Число черг графа -вимірного гіперкуба не перевищує . Число черг повних графів і повних двочасткових графів відоме точно — воно одно і відповідно.
Нерозв'язана проблема математики: Чи всі планарні графи мають обмежене число черг? (більше нерозв'язаних проблем математики) |
Будь-який граф з однією чергою є планарним графом з «дуговим рівневим» планарним вкладенням, у якому вершини розташовуються на паралельних прямих (рівнях), а кожне ребро або з'єднує вершини двох сусідніх рівнів, або утворює дугу, що з'єднує дві вершини на тому самому рівні. І тому, будь-який дуговий рівневий планарний граф має макет з однією чергою. Гіт, Лейтон і Розенберг припустили, що будь-який планарний граф має обмежену кількість черг, але підтвердження цього припущення поки що немає. Якщо число черг планарних графів обмежене, то це виконується і для 1-планарних графів і, більш того, для -планарних графів. Найсильніша межа, відома для числа черг планарних графів, не є сталою, вона дорівнює Полілогарифмічні межі числа черг відомі для графів з обмеженим родом та загальніших графів із мінорно замкнутих сімейств.
Якщо використати варіант числа черг, званий «сильним числом черг», число черг добутку графів можна обмежити функцією від числа черг та сильного числа черг множників добутку.
Пов'язані інваріанти
Графи з малим числом черг є розрідженими — графи з вершинами, що мають одну чергу, мають не більше ребер, а більш загального виду графи з числом черг мають не більше ребер. Звідси випливає, що ці графи мають мале хроматичне число. Зокрема графи з однією чергою мають розфарбування в 3 кольори, а графи з числом черг можуть вимагати не менше і не більше кольорів. І навпаки, межа числа ребер тягне за собою нижчу межу числа черг графа — число черг графів з вершинами і ребрами не перевищує . Межа близька до строгої, оскільки для випадкових -регулярних графів число черг із високою ймовірністю дорівнює
Нерозв'язана проблема математики: Чи повинен будь-який граф з обмеженою кількістю черг мати обмежену книжкову товщину і навпаки? (більше нерозв'язаних проблем математики) |
Графи з однією чергою мають книжкову товщину, що не перевищує двох. Для будь-якого фіксованого порядку вершин, добуток книжкової товщини та числа черг не менший від ширини перерізу графа, поділеного на максимальний степінь вершин. Книжкова товщина може бути значно більшою за кількість черг — трійкові графи Геммінга мають логарифмічне число черг, але поліноміальну книжкову товщину. Залишається невідомим, чи обмежена книжкова товщина будь-якою функцією від кількості черг. Гіт, Лейтон і Розенберг висловили припущення, що число черг не більше ніж лінійно залежить від книжкової товщини, але жодних досягнень у цьому напрямі немає. Відомо, що якщо всі двочасткові графи з 3-сторінковими книжковими вкладеннями мають обмежене число черг, то всі графи з обмеженою книжковою товщиною мають обмежене число черг.
Генлі і Гіт поставили питання, чи обмежене число черг графа функцією від його деревної ширини, і цитували неопубліковану дисертацію С. В. Пеммараджу як свідчення заперечної відповіді — планарні 3-дерева, що з'являються в цьому контексті, мають необмежене число черг. Проте число черг, як було показано, обмежене (двічі експоненційною) функцією від деревної ширини.
Обчислювальна складність
Визначення числа черг графа є NP-повною задачею. NP-повною задачею є навіть перевірка, що число черг дорівнює одиниці.
Однак, якщо порядок вершин попередньо задано, то оптимальне число черг дорівнює найбільшому числу ребер у -веселці, множині з ребер, у кожній парі яких одне ребро вкладене в інше (в описаному вище сенсі). Поділ ребер на черги можна здійснити, включивши ребро , яке є зовнішнім ребром -веселки (але не більшої веселки) в -ту чергу. Оптимальний макет можна побудувати за час , де — число вершин графа, а — число ребер.
Графи з обмеженим числом черг мають також обмежене розширення, що означає, що їх неглибокі мінори є розрідженими графами з відношенням ребер до вершин (або, еквівалентно, виродженістю або деревністю), обмеженим функцією від числа черг і глибини мінора. Як наслідок, деякі алгоритмічні задачі, включно із задачею ізоморфізму графів для графів обмеженого розміру, мають алгоритми лінійного часу виконання для таких графів. Загальніше, з огляду на обмежене розширення можна перевірити за лінійний час, чи є істинним твердження логіки першого порядку для графа з обмеженим числом черг.
Застосування у візуалізації графів
Хоча макети черг не обов'язково дають хороші двовимірні візуалізації, їх використовують для тривимірного подання графів. Зокрема, граф має обмежене число черг тоді й лише тоді, коли його вершини можна розташувати на тривимірній решітці розміром так, що жодні два ребра не перетинаються. Наприклад, графи де Брейна та графи з обмеженою деревною шириною мають тривимірне вкладення лінійного об'єму.
Логарифмічні або полілогарифмічні межі числа черг перетворюються при подібних вкладеннях у тривимірні решітки в майже лінійні об'єми, решітка в одному напрямку матиме лінійний розмір, а в двох інших — полілогарифмічний. Планарні графи, графи з обмеженим родом і графи з обмеженою локальною деревною шириною мають вкладення об'єму , тоді як графи замкнутих за мінорами сімейств мають об'єм .
Примітки
- Heath, Rosenberg, 1992.
- Auer, Bachmaier, Brandenburg, Brunner, 2011.
- Heath, Rosenberg, 1992, с. Proposition 4.1.
- Heath, Rosenberg, 1992, с. Propositions 4.2, 4.3.
- Heath, Leighton, Rosenberg, 1992.
- Rengarajan, Veni Madhavan, 1995.
- Heath, Rosenberg, 1992, с. Proposition 4.6.
- Heath, Rosenberg, 1992, Proposition 4.10; Hasunuma, Hirota, 2007; Pai, Chang, Wang, 2008; Gregor, Škrekovski, Vukašinović, 2011.
- Heath, Rosenberg, 1992, с. Propositions 4.7, 4.8.
- Heath, Rosenberg, 1992, с. Theorem 3.2.
- Dujmović, Wood, 2005.
- Дуймович (Dujmović, 2015), покращення ранішої межі Ді Батисти, Фраті і Паха (Di Battista, Frati, Pach, 2013).
- Dujmović, Morin, Wood, 2013.
- Wood, 2005.
- Heath, Rosenberg, 1992, с. Theorem 3.6.
- Dujmović, Wood, 2004.
- Heath, Leighton, Rosenberg, 1992. Алгоритм поліноміального часу для пошуку макета з близьким до цього числом черг дали Шарокі та Ші (Shahrokhi, Shi, 2000). Дуймович і Вуд (Dujmović, Wood, 2004) покращив сталу в цій межі до , де e — основа натурального логарифма.
- Wood, 2008.
- Ganley, Heath, 2001.
- Dujmović, Wood, 2003; Dujmović, Morin, Wood, 2005. Див. статтю Вуда (Wood, 2002) про слабший попередній результат, що обмежує число черг шляховою шириною або комбінацією деревної ширини та степеня графа.
- Heath, Rosenberg, 1992, с. Corollary 3.9.
- Heath, Rosenberg, 1992, с. Theorem 2.3.
- Nešetřil, Ossona de Mendez, Wood, 2012.
- Nešetřil, Ossona de Mendez, 2012, с. 321–327.
- Nešetřil, Ossona de Mendez, 2012, с. 401, Theorem 18.2.
- Wood, 2002; Dujmović, Pór, Wood, 2004; Dujmović, Morin, Wood, 2005. Див. Di Giacomo, Meijer, 2004 щодо жорсткіших меж розмірів решітки для графів із невеликим числом черг.
- Dujmović, Wood, 2003.
- Dujmović, Morin, Wood, 2005.
Література
- Christopher Auer, Christian Bachmaier, Franz Josef Brandenburg, Wolfgang Brunner, Andreas Gleißner. Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers. — Heidelberg : Springer, 2011. — Т. 6502. — С. 68–79. — (Lecture Notes in Computer Science) — DOI:
- Giuseppe Di Battista, Fabrizio Frati, János Pach. On the queue number of planar graphs // . — 2013. — Т. 42, вип. 6. — С. 2243–2285. — DOI: .
- Emilio Di Giacomo, Henk Meijer. Graph Drawing: 11th International Symposium, GD 2003 Perugia, Italy, September 21-24, 2003 Revised Papers. — Berlin : Springer, 2004. — Т. 2912. — С. 214–225. — (Lecture Notes in Computer Science) — DOI:
- Vida Dujmović. Graph layouts via layered separators // . — 2015. — Т. 110. — С. 79–89. — (Series B). — arXiv:1302.0304. — DOI: ..
- Vida Dujmović, Pat Morin, David R. Wood. Layout of graphs with bounded tree-width // . — 2005. — Т. 34, вип. 3. — С. 553–579. — arXiv:cs/0406024. — DOI: ..
- Vida Dujmović, Pat Morin, David R. Wood. Proceedings of the 54th IEEE Symposium on Foundations of Computer Science (FOCS ’13). — 2013. — С. 280–289. — DOI:.
- Vida Dujmović, Attila Pór, David R. Wood. Track layouts of graphs // Discrete Mathematics & Theoretical Computer Science. — 2004. — Т. 6, вип. 2. — С. 497–521..
- Vida Dujmović, David R. Wood. Graph-theoretic Concepts in Computer Science: 29th International Workshop, WG 2003. Elspeet, The Netherlands, June 19-21, 2003. Revised Papers. — Berlin : Springer, 2003. — Т. 2880. — С. 205–217. — (Lecture Notes in Computer Science) — DOI:.
- Vida Dujmović, David R. Wood. On linear layouts of graphs // Discrete Mathematics & Theoretical Computer Science. — 2004. — Т. 6, вип. 2. — С. 339–357..
- Vida Dujmović, David R. Wood. Stacks, queues and tracks: layouts of graph subdivisions // Discrete Mathematics & Theoretical Computer Science. — 2005. — Т. 7, вип. 1. — С. 155–201..
- Joseph L. Ganley, Lenwood S. Heath. The pagenumber of k-trees is O(k) // Discrete Applied Mathematics. — 2001. — Т. 109, вип. 3. — С. 215–221. — DOI: ..
- Petr Gregor, Riste Škrekovski, Vida Vukašinović. On the queue-number of the hypercube // Electronic Notes in Discrete Mathematics. — 2011. — Т. 38. — С. 413–418. — DOI: ..
- Toru Hasunuma, Misa Hirota. An improved upper bound on the queuenumber of the hypercube // Information Processing Letters. — 2007. — Т. 104, вип. 2. — С. 41–44. — DOI: ..
- Lenwood S. Heath, Frank Thomson Leighton, Arnold L. Rosenberg. Comparing queues and stacks as mechanisms[sic] for laying out graphs // SIAM Journal on Discrete Mathematics. — 1992. — Т. 5, вип. 3. — С. 398–412. — DOI: ..
- Lenwood S. Heath, Arnold L. Rosenberg. Laying out graphs using queues // . — 1992. — Т. 21, вип. 5. — С. 927–958. — DOI: ..
- Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms. — Springer, 2012. — Т. 28. — (Algorithms and Combinatorics) — . — DOI:.
- Jaroslav Nešetřil, Patrice Ossona de Mendez, David R. Wood. Characterisations and examples of graph classes with bounded expansion // European Journal of Combinatorics. — 2012. — Т. 33, вип. 3. — С. 350–373. — arXiv:0902.3265. — DOI: .
- Kung-Jui Pai, Jou-Ming Chang, Yue-Li Wang. A note on “An improved upper bound on the queuenumber of the hypercube” // Information Processing Letters. — 2008. — Т. 108, вип. 3. — С. 107–109. — DOI: .
- S. Rengarajan, C. E. Veni Madhavan. Computing and Combinatorics: First Annual International Conference, COCOON '95 Xi'an, China, August 24–26, 1995, Proceedings. — Berlin : Springer, 1995. — Т. 959. — С. 203–212. — (Lecture Notes in Computer Science) — DOI:.
- Farhad Shahrokhi, Weiping Shi. On crossing sets, disjoint sets, and pagenumber // Journal of Algorithms. — 2000. — Т. 34, вип. 1. — С. 40–53. — DOI: .
- David R. Wood. FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science, 22nd Conference Kanpur, India, December 12–14, 2002, Proceedings. — Berlin : Springer, 2002. — Т. 2556. — С. 348–359. — (Lecture Notes in Computer Science) — DOI:
- David R. Wood. Queue layouts of graph products and powers // Discrete Mathematics & Theoretical Computer Science. — 2005. — Т. 7, вип. 1. — С. 255–268..
- David R. Wood. Bounded-degree graphs have arbitrarily large queue-number // Discrete Mathematics & Theoretical Computer Science. — 2008. — Т. 10, вип. 1. — С. 27–34. — arXiv:math/0601293.[недоступне посилання з Апрель 2018].
Посилання
- Problem 52: Queue-Number of Planar Graphs, The Open Problems Project
- Stack and Queue Layouts — проблеми, представлені влітку 2009, Research Experiences for Graduate Students, Douglas B. West
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Chislo cherg grafa ce invariant grafa viznachenij analogichno stekovomu chislu tovshini knigi i vikoristovuye vporyadkuvannya FIFO pershij uvijshov pershij vijshov cherga zamist uporyadkuvannya LIFO ostannim uvijshov pershim vijshov stek Graf de Brejna Dlya navedenogo vporyadkuvannya rozpodil reber na dvi mnozhini sho jdut livoruch i pravoruch vid vershin ye shemoyu 2 cherg cogo grafa ViznachennyaPodannya zadanogo grafa yak cherg maket cherg viznachayetsya povnim uporyadkuvannyam vershin grafa razom iz rozkladannyam reber grafa na kilka cherg Potribno shobi mnozhini reber kozhnoyi z cherg ne mali vkladenosti za poryadkom vershin u tomu sensi sho yaksho a b displaystyle ab i c d displaystyle cd dva rebra v odnij cherzi to ne povinno buti a lt c lt d lt b displaystyle a lt c lt d lt b Chislo cherg q n G displaystyle qn G grafa G displaystyle G ce najmenshe chislo cherg podannya grafa u viglyadi cherg Vikoristovuyuchi maket cherg grafa mozhna perebrati rebra okremoyi chergi zastosovuyuchi standartnu strukturu cherg shlyahom pereboru vershin u zadanomu poryadku i koli dosyagayemo vershini vibirayemo vsi rebra dlya yakih vershina ye drugoyu vershinoyu dugi i zanosimo v chergu dugi dlya yakih vershina ye pershoyu Umova vidsutnosti vkladenosti zabezpechuye sho z dosyagnennyam vershini vse rebra sho mayut cyu vershinu yak kincevu perebuvayut u cherzi i gotovi do vibirannya Rozklad grafa na chergi z opisanimi vlastivostyami mozhna vvazhati alternativnim viznachennyam Inshe ekvivalentne viznachennya maketa cherg vikoristovuye ponyattya vkladennya zadanogo grafa v cilindr iz vershinami roztashovanimi na pryamij sho lezhit na poverhni cilindra a kozhne rebro oginaye cilindr Rebra vklyucheni v odnu chergu ne povinni peretinatisya ale peretini reber riznih cherg dozvoleno Maket cherg uveli Git i Rozenberg za analogiyeyu z poperednoyu robotoyu pro knizhkovi vkladennya grafiv yaki viznachayutsya v toj samij sposib z vikoristannyam stekiv zamist cherg Yak voni zaznachili ci maketi takozh pov yazani z rannimi robotami pro sortuvannya perestanovok iz vikoristannyam paralelnih cherg i do stvorennya pov yazane z rozrobkoyu integralnih shem ta upravlinnyam zv yazkami v en Klasi grafiv z obmezhenoyu kilkistyu chergBud yake derevo maye chislo cherg sho dorivnyuye 1 z uporyadkuvannyam vershin zadanim poshukom u shirinu U psevdolisiv i reshitok chislo cherg takozh dorivnyuye 1 Chislo cherg zovniplanarnih grafiv ne perevishuye 2 Sonyachnij 3 graf trikutnik kozhne rebro yakogo zamineno trikutnikom ye prikladom zovniplanarnogo grafa chislo cherg yakogo dorivnyuye 2 Chislo cherg paralelno poslidovnogo grafa ne perevishuye 3 Chislo cherg dvijkovih grafiv de Brejna dorivnyuye 2 Chislo cherg grafa d displaystyle d vimirnogo giperkuba ne perevishuye d 1 displaystyle d 1 Chislo cherg povnih grafiv K n displaystyle K n i povnih dvochastkovih grafiv K a b displaystyle K a b vidome tochno vono odno n 2 displaystyle lfloor n 2 rfloor i min a 2 b 2 displaystyle min lceil a 2 rceil lceil b 2 rceil vidpovidno Nerozv yazana problema matematiki Chi vsi planarni grafi mayut obmezhene chislo cherg bilshe nerozv yazanih problem matematiki Bud yakij graf z odniyeyu chergoyu ye planarnim grafom z dugovim rivnevim planarnim vkladennyam u yakomu vershini roztashovuyutsya na paralelnih pryamih rivnyah a kozhne rebro abo z yednuye vershini dvoh susidnih rivniv abo utvoryuye dugu sho z yednuye dvi vershini na tomu samomu rivni I tomu bud yakij dugovij rivnevij planarnij graf maye maket z odniyeyu chergoyu Git Lejton i Rozenberg pripustili sho bud yakij planarnij graf maye obmezhenu kilkist cherg ale pidtverdzhennya cogo pripushennya poki sho nemaye Yaksho chislo cherg planarnih grafiv obmezhene to ce vikonuyetsya i dlya 1 planarnih grafiv i bilsh togo dlya k displaystyle k planarnih grafiv Najsilnisha mezha vidoma dlya chisla cherg planarnih grafiv ne ye staloyu vona dorivnyuye O log n displaystyle O log n Polilogarifmichni mezhi chisla cherg vidomi dlya grafiv z obmezhenim rodom ta zagalnishih grafiv iz minorno zamknutih simejstv Yaksho vikoristati variant chisla cherg zvanij silnim chislom cherg chislo cherg dobutku grafiv mozhna obmezhiti funkciyeyu vid chisla cherg ta silnogo chisla cherg mnozhnikiv dobutku Pov yazani invariantiGrafi z malim chislom cherg ye rozridzhenimi grafi z n displaystyle n vershinami sho mayut odnu chergu mayut ne bilshe 2 n 3 displaystyle 2n 3 reber a bilsh zagalnogo vidu grafi z chislom cherg q displaystyle q mayut ne bilshe 2 q n q 2 q 1 displaystyle 2qn q 2q 1 reber Zvidsi viplivaye sho ci grafi mayut male hromatichne chislo Zokrema grafi z odniyeyu chergoyu mayut rozfarbuvannya v 3 kolori a grafi z chislom cherg q displaystyle q mozhut vimagati ne menshe 2 q 1 displaystyle 2q 1 i ne bilshe 4 q displaystyle 4q koloriv I navpaki mezha chisla reber tyagne za soboyu nizhchu mezhu chisla cherg grafa chislo cherg grafiv z n displaystyle n vershinami i m displaystyle m rebrami ne perevishuye O m displaystyle O sqrt m Mezha blizka do strogoyi oskilki dlya vipadkovih d displaystyle d regulyarnih grafiv chislo cherg iz visokoyu jmovirnistyu dorivnyuye W d n n 1 d displaystyle Omega left frac sqrt dn n 1 d right Nerozv yazana problema matematiki Chi povinen bud yakij graf z obmezhenoyu kilkistyu cherg mati obmezhenu knizhkovu tovshinu i navpaki bilshe nerozv yazanih problem matematiki Grafi z odniyeyu chergoyu mayut knizhkovu tovshinu sho ne perevishuye dvoh Dlya bud yakogo fiksovanogo poryadku vershin dobutok knizhkovoyi tovshini ta chisla cherg ne menshij vid shirini pererizu grafa podilenogo na maksimalnij stepin vershin Knizhkova tovshina mozhe buti znachno bilshoyu za kilkist cherg trijkovi grafi Gemminga mayut logarifmichne chislo cherg ale polinomialnu knizhkovu tovshinu Zalishayetsya nevidomim chi obmezhena knizhkova tovshina bud yakoyu funkciyeyu vid kilkosti cherg Git Lejton i Rozenberg vislovili pripushennya sho chislo cherg ne bilshe nizh linijno zalezhit vid knizhkovoyi tovshini ale zhodnih dosyagnen u comu napryami nemaye Vidomo sho yaksho vsi dvochastkovi grafi z 3 storinkovimi knizhkovimi vkladennyami mayut obmezhene chislo cherg to vsi grafi z obmezhenoyu knizhkovoyu tovshinoyu mayut obmezhene chislo cherg Genli i Git postavili pitannya chi obmezhene chislo cherg grafa funkciyeyu vid jogo derevnoyi shirini i cituvali neopublikovanu disertaciyu S V Pemmaradzhu yak svidchennya zaperechnoyi vidpovidi planarni 3 dereva sho z yavlyayutsya v comu konteksti mayut neobmezhene chislo cherg Prote chislo cherg yak bulo pokazano obmezhene dvichi eksponencijnoyu funkciyeyu vid derevnoyi shirini Obchislyuvalna skladnistViznachennya chisla cherg grafa ye NP povnoyu zadacheyu NP povnoyu zadacheyu ye navit perevirka sho chislo cherg dorivnyuye odinici Odnak yaksho poryadok vershin poperedno zadano to optimalne chislo cherg dorivnyuye najbilshomu chislu reber u k displaystyle k veselci mnozhini z k displaystyle k reber u kozhnij pari yakih odne rebro vkladene v inshe v opisanomu vishe sensi Podil reber na chergi mozhna zdijsniti vklyuchivshi rebro e displaystyle e yake ye zovnishnim rebrom i displaystyle i veselki ale ne bilshoyi veselki v i displaystyle i tu chergu Optimalnij maket mozhna pobuduvati za chas O m log log n displaystyle O m log log n de n displaystyle n chislo vershin grafa a m displaystyle m chislo reber Grafi z obmezhenim chislom cherg mayut takozh obmezhene rozshirennya sho oznachaye sho yih negliboki minori ye rozridzhenimi grafami z vidnoshennyam reber do vershin abo ekvivalentno virodzhenistyu abo derevnistyu obmezhenim funkciyeyu vid chisla cherg i glibini minora Yak naslidok deyaki algoritmichni zadachi vklyuchno iz zadacheyu izomorfizmu grafiv dlya grafiv obmezhenogo rozmiru mayut algoritmi linijnogo chasu vikonannya dlya takih grafiv Zagalnishe z oglyadu na obmezhene rozshirennya mozhna pereviriti za linijnij chas chi ye istinnim tverdzhennya logiki pershogo poryadku dlya grafa z obmezhenim chislom cherg Zastosuvannya u vizualizaciyi grafivHocha maketi cherg ne obov yazkovo dayut horoshi dvovimirni vizualizaciyi yih vikoristovuyut dlya trivimirnogo podannya grafiv Zokrema graf G displaystyle G maye obmezhene chislo cherg todi j lishe todi koli jogo vershini mozhna roztashuvati na trivimirnij reshitci rozmirom O n O 1 O 1 displaystyle O n times O 1 times O 1 tak sho zhodni dva rebra ne peretinayutsya Napriklad grafi de Brejna ta grafi z obmezhenoyu derevnoyu shirinoyu mayut trivimirne vkladennya linijnogo ob yemu Logarifmichni abo polilogarifmichni mezhi chisla cherg peretvoryuyutsya pri podibnih vkladennyah u trivimirni reshitki v majzhe linijni ob yemi reshitka v odnomu napryamku matime linijnij rozmir a v dvoh inshih polilogarifmichnij Planarni grafi grafi z obmezhenim rodom i grafi z obmezhenoyu lokalnoyu derevnoyu shirinoyu mayut vkladennya ob yemu O n log n displaystyle O n log n todi yak grafi zamknutih za minorami simejstv mayut ob yem O n log O 1 n displaystyle O n log O 1 n PrimitkiHeath Rosenberg 1992 Auer Bachmaier Brandenburg Brunner 2011 Heath Rosenberg 1992 s Proposition 4 1 Heath Rosenberg 1992 s Propositions 4 2 4 3 Heath Leighton Rosenberg 1992 Rengarajan Veni Madhavan 1995 Heath Rosenberg 1992 s Proposition 4 6 Heath Rosenberg 1992 Proposition 4 10 Hasunuma Hirota 2007 Pai Chang Wang 2008 Gregor Skrekovski Vukasinovic 2011 Heath Rosenberg 1992 s Propositions 4 7 4 8 Heath Rosenberg 1992 s Theorem 3 2 Dujmovic Wood 2005 Dujmovich Dujmovic 2015 pokrashennya ranishoyi mezhi Di Batisti Frati i Paha Di Battista Frati Pach 2013 Dujmovic Morin Wood 2013 Wood 2005 Heath Rosenberg 1992 s Theorem 3 6 Dujmovic Wood 2004 Heath Leighton Rosenberg 1992 Algoritm polinomialnogo chasu dlya poshuku maketa z blizkim do cogo chislom cherg dali Sharoki ta Shi Shahrokhi Shi 2000 Dujmovich i Vud Dujmovic Wood 2004 pokrashiv stalu v cij mezhi do e m displaystyle e sqrt m de e osnova naturalnogo logarifma Wood 2008 Ganley Heath 2001 Dujmovic Wood 2003 Dujmovic Morin Wood 2005 Div stattyu Vuda Wood 2002 pro slabshij poperednij rezultat sho obmezhuye chislo cherg shlyahovoyu shirinoyu abo kombinaciyeyu derevnoyi shirini ta stepenya grafa Heath Rosenberg 1992 s Corollary 3 9 Heath Rosenberg 1992 s Theorem 2 3 Nesetril Ossona de Mendez Wood 2012 Nesetril Ossona de Mendez 2012 s 321 327 Nesetril Ossona de Mendez 2012 s 401 Theorem 18 2 Wood 2002 Dujmovic Por Wood 2004 Dujmovic Morin Wood 2005 Div Di Giacomo Meijer 2004 shodo zhorstkishih mezh rozmiriv reshitki dlya grafiv iz nevelikim chislom cherg Dujmovic Wood 2003 Dujmovic Morin Wood 2005 LiteraturaChristopher Auer Christian Bachmaier Franz Josef Brandenburg Wolfgang Brunner Andreas Gleissner Graph Drawing 18th International Symposium GD 2010 Konstanz Germany September 21 24 2010 Revised Selected Papers Heidelberg Springer 2011 T 6502 S 68 79 Lecture Notes in Computer Science DOI 10 1007 978 3 642 18469 7 7 Giuseppe Di Battista Fabrizio Frati Janos Pach On the queue number of planar graphs 2013 T 42 vip 6 S 2243 2285 DOI 10 1137 130908051 Emilio Di Giacomo Henk Meijer Graph Drawing 11th International Symposium GD 2003 Perugia Italy September 21 24 2003 Revised Papers Berlin Springer 2004 T 2912 S 214 225 Lecture Notes in Computer Science DOI 10 1007 978 3 540 24595 7 20 Vida Dujmovic Graph layouts via layered separators 2015 T 110 S 79 89 Series B arXiv 1302 0304 DOI 10 1016 j jctb 2014 07 005 Vida Dujmovic Pat Morin David R Wood Layout of graphs with bounded tree width 2005 T 34 vip 3 S 553 579 arXiv cs 0406024 DOI 10 1137 S0097539702416141 Vida Dujmovic Pat Morin David R Wood Proceedings of the 54th IEEE Symposium on Foundations of Computer Science FOCS 13 2013 S 280 289 DOI 10 1109 FOCS 2013 38 Vida Dujmovic Attila Por David R Wood Track layouts of graphs Discrete Mathematics amp Theoretical Computer Science 2004 T 6 vip 2 S 497 521 Vida Dujmovic David R Wood Graph theoretic Concepts in Computer Science 29th International Workshop WG 2003 Elspeet The Netherlands June 19 21 2003 Revised Papers Berlin Springer 2003 T 2880 S 205 217 Lecture Notes in Computer Science DOI 10 1007 978 3 540 39890 5 18 Vida Dujmovic David R Wood On linear layouts of graphs Discrete Mathematics amp Theoretical Computer Science 2004 T 6 vip 2 S 339 357 Vida Dujmovic David R Wood Stacks queues and tracks layouts of graph subdivisions Discrete Mathematics amp Theoretical Computer Science 2005 T 7 vip 1 S 155 201 Joseph L Ganley Lenwood S Heath The pagenumber of k trees is O k Discrete Applied Mathematics 2001 T 109 vip 3 S 215 221 DOI 10 1016 S0166 218X 00 00178 5 Petr Gregor Riste Skrekovski Vida Vukasinovic On the queue number of the hypercube Electronic Notes in Discrete Mathematics 2011 T 38 S 413 418 DOI 10 1016 j endm 2011 09 067 Toru Hasunuma Misa Hirota An improved upper bound on the queuenumber of the hypercube Information Processing Letters 2007 T 104 vip 2 S 41 44 DOI 10 1016 j ipl 2007 05 006 Lenwood S Heath Frank Thomson Leighton Arnold L Rosenberg Comparing queues and stacks as mechanisms sic for laying out graphs SIAM Journal on Discrete Mathematics 1992 T 5 vip 3 S 398 412 DOI 10 1137 0405031 Lenwood S Heath Arnold L Rosenberg Laying out graphs using queues 1992 T 21 vip 5 S 927 958 DOI 10 1137 0221055 Jaroslav Nesetril Patrice Ossona de Mendez Sparsity Graphs Structures and Algorithms Springer 2012 T 28 Algorithms and Combinatorics ISBN 978 3 642 27874 7 DOI 10 1007 978 3 642 27875 4 Jaroslav Nesetril Patrice Ossona de Mendez David R Wood Characterisations and examples of graph classes with bounded expansion European Journal of Combinatorics 2012 T 33 vip 3 S 350 373 arXiv 0902 3265 DOI 10 1016 j ejc 2011 09 008 Kung Jui Pai Jou Ming Chang Yue Li Wang A note on An improved upper bound on the queuenumber of the hypercube Information Processing Letters 2008 T 108 vip 3 S 107 109 DOI 10 1016 j ipl 2008 04 019 S Rengarajan C E Veni Madhavan Computing and Combinatorics First Annual International Conference COCOON 95 Xi an China August 24 26 1995 Proceedings Berlin Springer 1995 T 959 S 203 212 Lecture Notes in Computer Science DOI 10 1007 BFb0030834 Farhad Shahrokhi Weiping Shi On crossing sets disjoint sets and pagenumber Journal of Algorithms 2000 T 34 vip 1 S 40 53 DOI 10 1006 jagm 1999 1049 David R Wood FST TCS 2002 Foundations of Software Technology and Theoretical Computer Science 22nd Conference Kanpur India December 12 14 2002 Proceedings Berlin Springer 2002 T 2556 S 348 359 Lecture Notes in Computer Science DOI 10 1007 3 540 36206 1 31 David R Wood Queue layouts of graph products and powers Discrete Mathematics amp Theoretical Computer Science 2005 T 7 vip 1 S 255 268 David R Wood Bounded degree graphs have arbitrarily large queue number Discrete Mathematics amp Theoretical Computer Science 2008 T 10 vip 1 S 27 34 arXiv math 0601293 nedostupne posilannya z Aprel 2018 PosilannyaProblem 52 Queue Number of Planar Graphs The Open Problems Project Stack and Queue Layouts problemi predstavleni vlitku 2009 Research Experiences for Graduate Students Douglas B West