Число черг графа

Граф де Брейна. Для наведеного впорядкування розподіл ребер на дві множини, що йдуть ліворуч і праворуч від вершин, є схемою 2 черг цього графа.

Число черг графа — це інваріант графа, визначений аналогічно стековому числу (товщині книги) і використовує впорядкування FIFO (перший увійшов, перший вийшов, черга) замість упорядкування LIFO (останнім увійшов, першим вийшов, стек).

Визначення

Подання заданого графа як черг (макет черг) визначається повним упорядкуванням вершин графа разом із розкладанням ребер графа на кілька «черг». Потрібно, щоби множини ребер кожної з черг не мали вкладеності за порядком вершин у тому сенсі, що якщо $ab$ і $cd$ — два ребра в одній черзі, то не повинно бути $a<c<d<b$. Число черг $qn(G)$ графа $G$ — це найменше число черг подання графа у вигляді черг.

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

Макет черг увели Гіт і Розенберг за аналогією з попередньою роботою про книжкові вкладення графів, які визначаються в той самий спосіб з використанням стеків замість черг. Як вони зазначили, ці макети також пов'язані з ранніми роботами про сортування перестановок із використанням паралельних черг і до створення пов'язане з розробкою інтегральних схем та управлінням зв'язками в розподілених алгоритмах.

Класи графів з обмеженою кількістю черг

Будь-яке дерево має число черг, що дорівнює 1 з упорядкуванням вершин, заданим пошуком у ширину. У псевдолісів і решіток число черг також дорівнює 1. Число черг зовніпланарних графів не перевищує 2. Сонячний 3-граф (трикутник, кожне ребро якого замінено трикутником) є прикладом зовніпланарного графа, число черг якого дорівнює 2. Число черг паралельно-послідовного графа не перевищує 3.

Число черг двійкових графів де Брейна дорівнює 2. Число черг графа $d$-вимірного гіперкуба не перевищує $d-1$. Число черг повних графів $K_{n}$ і повних двочасткових графів $K_{a,b}$ відоме точно — воно одно $\lfloor n/2\rfloor$ і $\min\{\lceil a/2\rceil ,\lceil b/2\rceil \}$ відповідно.

Нерозв'язана проблема математики: Чи всі планарні графи мають обмежене число черг? (більше нерозв'язаних проблем математики)

Будь-який граф з однією чергою є планарним графом з «дуговим рівневим» планарним вкладенням, у якому вершини розташовуються на паралельних прямих (рівнях), а кожне ребро або з'єднує вершини двох сусідніх рівнів, або утворює дугу, що з'єднує дві вершини на тому самому рівні. І тому, будь-який дуговий рівневий планарний граф має макет з однією чергою. Гіт, Лейтон і Розенберг припустили, що будь-який планарний граф має обмежену кількість черг, але підтвердження цього припущення поки що немає. Якщо число черг планарних графів обмежене, то це виконується і для 1-планарних графів і, більш того, для $k$-планарних графів. Найсильніша межа, відома для числа черг планарних графів, не є сталою, вона дорівнює $O(\log n)$ Полілогарифмічні межі числа черг відомі для графів з обмеженим родом та загальніших графів із мінорно замкнутих сімейств.

Якщо використати варіант числа черг, званий «сильним числом черг», число черг добутку графів можна обмежити функцією від числа черг та сильного числа черг множників добутку.

Пов'язані інваріанти

Графи з малим числом черг є розрідженими — графи з $n$ вершинами, що мають одну чергу, мають не більше $2n-3$ ребер, а більш загального виду графи з числом черг $q$ мають не більше $2qn-q(2q+1)$ ребер. Звідси випливає, що ці графи мають мале хроматичне число. Зокрема графи з однією чергою мають розфарбування в 3 кольори, а графи з числом черг $q$ можуть вимагати не менше $2q+1$ і не більше $4q$ кольорів. І навпаки, межа числа ребер тягне за собою нижчу межу числа черг графа — число черг графів з $n$ вершинами і $m$ ребрами не перевищує $O({\sqrt {m}})$. Межа близька до строгої, оскільки для випадкових $d$-регулярних графів число черг із високою ймовірністю дорівнює

$\Omega \left({\frac {\sqrt {dn}}{n^{1/d}}}\right).$

Нерозв'язана проблема математики: Чи повинен будь-який граф з обмеженою кількістю черг мати обмежену книжкову товщину і навпаки? (більше нерозв'язаних проблем математики)

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

Генлі і Гіт поставили питання, чи обмежене число черг графа функцією від його деревної ширини, і цитували неопубліковану дисертацію С. В. Пеммараджу як свідчення заперечної відповіді — планарні 3-дерева, що з'являються в цьому контексті, мають необмежене число черг. Проте число черг, як було показано, обмежене (двічі експоненційною) функцією від деревної ширини.

Обчислювальна складність

Визначення числа черг графа є NP-повною задачею. NP-повною задачею є навіть перевірка, що число черг дорівнює одиниці.

Однак, якщо порядок вершин попередньо задано, то оптимальне число черг дорівнює найбільшому числу ребер у $k$-веселці, множині з $k$ ребер, у кожній парі яких одне ребро вкладене в інше (в описаному вище сенсі). Поділ ребер на черги можна здійснити, включивши ребро $e$, яке є зовнішнім ребром $i$-веселки (але не більшої веселки) в $i$-ту чергу. Оптимальний макет можна побудувати за час $O(m\log \log n)$, де $n$ — число вершин графа, а $m$ — число ребер.

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

Застосування у візуалізації графів

Хоча макети черг не обов'язково дають хороші двовимірні візуалізації, їх використовують для тривимірного подання графів. Зокрема, граф $G$ має обмежене число черг тоді й лише тоді, коли його вершини можна розташувати на тривимірній решітці розміром $O(n)\times O(1)\times O(1)$ так, що жодні два ребра не перетинаються. Наприклад, графи де Брейна та графи з обмеженою деревною шириною мають тривимірне вкладення лінійного об'єму.

Логарифмічні або полілогарифмічні межі числа черг перетворюються при подібних вкладеннях у тривимірні решітки в майже лінійні об'єми, решітка в одному напрямку матиме лінійний розмір, а в двох інших — полілогарифмічний. Планарні графи, графи з обмеженим родом і графи з обмеженою локальною деревною шириною мають вкладення об'єму $O(n\log n)$, тоді як графи замкнутих за мінорами сімейств мають об'єм $O(n\log ^{O(1)}n)$.

Література

• 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:10.1007/978-3-642-18469-7_7.
• Giuseppe Di Battista, Fabrizio Frati, János Pach. On the queue number of planar graphs // SIAM Journal on Computing. — 2013. — Т. 42, вип. 6. — С. 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. — Т. 2912. — С. 214–225. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-540-24595-7_20.
• Vida Dujmović. Graph layouts via layered separators // Journal of Combinatorial Theory. — 2015. — Т. 110. — С. 79–89. — (Series B). — arXiv:1302.0304. — DOI:10.1016/j.jctb.2014.07.005..
• Vida Dujmović, Pat Morin, David R. Wood. Layout of graphs with bounded tree-width // SIAM Journal on Computing. — 2005. — Т. 34, вип. 3. — С. 553–579. — arXiv:cs/0406024. — DOI:10.1137/S0097539702416141..
• Vida Dujmović, Pat Morin, David R. Wood. Proceedings of the 54th IEEE Symposium on Foundations of Computer Science (FOCS ’13). — 2013. — С. 280–289. — DOI:10.1109/FOCS.2013.38..
• 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:10.1007/978-3-540-39890-5_18..
• 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:10.1016/S0166-218X(00)00178-5..
• Petr Gregor, Riste Škrekovski, Vida Vukašinović. On the queue-number of the hypercube // Electronic Notes in Discrete Mathematics. — 2011. — Т. 38. — С. 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. — Т. 104, вип. 2. — С. 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. — Т. 5, вип. 3. — С. 398–412. — DOI:10.1137/0405031..
• Lenwood S. Heath, Arnold L. Rosenberg. Laying out graphs using queues // SIAM Journal on Computing. — 1992. — Т. 21, вип. 5. — С. 927–958. — DOI:10.1137/0221055..
• Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms. — Springer, 2012. — Т. 28. — (Algorithms and Combinatorics) — ISBN 978-3-642-27874-7. — DOI:10.1007/978-3-642-27875-4..
• 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: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. — Т. 108, вип. 3. — С. 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. — Т. 959. — С. 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. — Т. 34, вип. 1. — С. 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. — Т. 2556. — С. 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 & 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