Номер очереди

Граф де Брейна . При показанном порядке вершин разбиение ребер на два подмножества, охватывающих левую и правую стороны рисунка, представляет собой двухочередную компоновку этого графа.

В математической области теории графов номер очереди графа — это инвариант графа , определяемый аналогично номеру стопки (толщине книги) с использованием упорядочения «первым пришел — первым ушел» (очередь) вместо упорядочения «последним пришел — первым ушел» (стек).

Определение

Макет очереди данного графа определяется общим порядком вершин графа вместе с разбиением ребер на несколько «очередей». Набор ребер в каждой очереди требуется для избежания ребер, которые правильно вложены: если $ab$ и $cd — два ребра в одной очереди,$ то не должно быть возможности иметь $a$ $<$ $c$ $<$ $d$ $<$ $b$ в порядке вершин. Номер очереди $qn($ $G$ $)$ графа $G$ — это минимальное количество очередей в макете очереди. ^[1]

Эквивалентно, из макета очереди можно было бы обрабатывать ребра в одной очереди, используя структуру данных очереди , рассматривая вершины в их заданном порядке, и при достижении вершины, исключая из очереди все ребра, для которых она является второй конечной точкой, а затем помещая в очередь все ребра, для которых она является первой конечной точкой. Условие вложенности гарантирует, что при достижении вершины все ребра, для которых она является второй конечной точкой, готовы к исключению из очереди. ^[1] Другое эквивалентное определение макетов очереди включает в себя встраивание данного графа в цилиндр , с вершинами, размещенными на линии в цилиндре, и с каждым ребром, обернутым один раз вокруг цилиндра. Ребра, назначенные одной очереди, не могут пересекаться друг с другом, но пересечения разрешены между ребрами, принадлежащими разным очередям. ^[2]

Макеты очередей были определены Хитом и Розенбергом (1992) по аналогии с предыдущей работой по книжным вложениям графов, которые можно определить таким же образом, используя стеки вместо очередей. Как они заметили, эти макеты также связаны с более ранней работой по сортировке перестановок с использованием систем параллельных очередей и могут быть мотивированы приложениями в проектировании СБИС и управлении коммуникациями для распределенных алгоритмов . ^[1]

Графические классы с ограниченным числом очередей

Каждое дерево имеет очередь номер 1, с порядком вершин, заданным обходом в ширину . ^[3] Псевдолеса и решетчатые графы также имеют очередь номер 1. ^[4] Внешнепланарные графы имеют очередь номер не более 2; 3-солнечный граф (треугольник, каждое из ребер которого заменено треугольником) является примером внешнепланарного графа, очередь которого номер точно равен 2. ^[5] Последовательно-параллельные графы имеют очередь номер не более 3, ^[6] в то время как очередь планарных 3-деревьев номер не более 5. ^[7]

Бинарные графы де Брейна имеют очередь номер 2. ^[8] Граф d -мерного гиперкуба имеет очередь номер не более . ^[9] Номера очередей полных графов K _n и полных двудольных графов K _a_,_b известны точно: они равны и соответственно. ^[10] $d-\lfloor \log _{2}d\rfloor$ $\lfloor n/2\rfloor$ $\min\{\lceil a/2\rceil,\lceil b/2\rceil \}$

Каждый 1-очередной граф является планарным графом с «дуговым выровненным» планарным вложением, в котором вершины размещены на параллельных линиях (уровнях), и каждое ребро либо соединяет вершины на двух последовательных уровнях, либо образует дугу, которая соединяет две вершины на одном уровне, обходя все предыдущие уровни. Наоборот, каждый дуговой выровненный планарный граф имеет 1-очередную компоновку. ^[11] В 1992 году Хит, Лейтон и Розенберг (1992) выдвинули гипотезу, что каждый планарный граф имеет ограниченное число очередей. Эта гипотеза была положительно разрешена в 2019 году Дуймовичем и др. (2020), которые показали, что планарные графы и, в более общем смысле, каждый собственный минорно-замкнутый класс графов имеет ограниченное число очередей. В частности, Дуймович и др. (2020) доказали, что число очередей планарных графов не превышает 49, а Бекос, Гронеманн и Рафтопулу (2021) снизили эту границу до 42.

Используя вариацию номера очереди, называемую сильным номером очереди, номер очереди графового произведения может быть ограничен функцией номеров очередей и сильных номеров очередей факторов в произведении. ^[12]

Связанные инварианты

Графы с малым числом очередей являются разреженными графами : графы с 1 очередью и $n$ вершинами имеют не более $2 n - 3$ ребер, ^[13] и, в более общем случае, графы с числом очередей $q$ имеют не более $2 qn - q (2 q + 1)$ ребер. ^[14] Это подразумевает, что эти графы также имеют малое хроматическое число : в частности, графы с 1 очередью являются 3-раскрашиваемыми, а графы с числом очередей $q$ могут нуждаться не менее $2 q + 1$ и не более $4 q$ цветов. ^[14] В другом направлении ограничение на число ребер подразумевает гораздо более слабую границу на число очередей: графы с $n$ вершинами и $m$ ребрами имеют число очередей не более ⁠ ⁠ $O({\sqrt {м}})$ . ^[15] Эта граница близка к жесткой, поскольку для случайных $d$ -регулярных графов число очередей с высокой вероятностью равно

\Омега \left({\frac {\sqrt {dn}}{n^{1/d}}}\right).

^[16]

Нерешенная задача по математике :

Должен ли каждый граф с ограниченной толщиной книги иметь также ограниченное число очередей?

(еще нерешенные проблемы по математике)

Графы с числом очереди 1 имеют книжную толщину не более 2. ^[17] Для любого фиксированного порядка вершин произведение книжной толщины и числа очередей для этого порядка не менее ширины разреза графа, деленной на его максимальную степень. ^[18] Книжная толщина может быть намного больше числа очередей: тернарные графы Хэмминга имеют логарифмическое число очередей, но полиномиально большую книжную толщину ^[18], и существуют графы с числом очереди 4, которые имеют произвольно большую книжную толщину. ^[17] Хит, Лейтон и Розенберг (1992) предположили, что число очередей является не более чем линейной функцией книжной толщины, но функциональная граница в этом направлении неизвестна. Известно, что если все двудольные графы с 3-страничными книжными вложениями имеют ограниченное число очередей, то все графы с ограниченной книжной толщиной имеют ограниченное число очередей. ^[19]

Ganley & Heath (2001) задались вопросом, может ли число очередей графа быть ограничено как функция его ширины дерева , и процитировали неопубликованную докторскую диссертацию SV Pemmaraju как доказательство того, что ответ был отрицательным: планарные 3-деревья, по-видимому, из этого доказательства имели неограниченное число очередей. Однако впоследствии было показано, что число очередей ограничено (двойной экспоненциальной) функцией ширины дерева. ^[20]

Сложность вычислений

Определение номера очереди заданного графа или даже проверка того, равно ли это число 1, является NP-полной задачей . ^[21]

Однако, если порядок вершин макета очереди задан как часть ввода, то оптимальное количество очередей для макета равно максимальному количеству ребер в $k$ -радуге , наборе из $k$ ребер, каждые два из которых образуют вложенную пару. Разбиение ребер на очереди может быть выполнено путем назначения ребра $e$ , которое является внешним краем $i$ -радуги (и не большей радуги) для $i$ -й очереди. Можно построить оптимальную компоновку за время $O (m log(log n))$ , где $n$ обозначает количество вершин входного графа, а $m$ обозначает количество ребер. ^[22]

Графы с ограниченным числом очередей также имеют ограниченное расширение , что означает, что их неглубокие миноры являются разреженными графами с отношением ребер к вершинам (или, что эквивалентно, вырожденностью или древесностью ), которое ограничено функцией числа очередей и глубиной минора. Как следствие, несколько алгоритмических проблем, включая изоморфизм подграфов для графов шаблонов ограниченного размера, имеют линейные алгоритмы времени для этих графов. ^[23] В более общем смысле, из-за их ограниченного расширения, можно проверить, является ли любое предложение в логике первого порядка графов допустимым для данного графа с ограниченным числом очередей, за линейное время. ^[24]

Применение в графическом рисовании

Хотя макеты очередей не обязательно создают хорошие рисунки двумерных графов , они использовались для рисования трехмерных графов. В частности, класс графов $X$ имеет ограниченное число очередей тогда и только тогда, когда для каждого $n-$ вершинного графа $G$ в $X$ возможно разместить вершины $G$ в трехмерной сетке размерностей $O (n) \times O (1) \times O (1)$ так, чтобы никакие два ребра (при прямом рисовании) не пересекали друг друга. ^[25] Так, например, графы де Брейна , графы ограниченной древовидной ширины, планарные графы и правильные семейства минорно-замкнутых графов имеют трехмерные вложения линейного объема. ^[26]^[27]^[28]

Примечания

^ abc Хит и Розенберг (1992).
^ Ауэр и др. (2011).
^ Хит и Розенберг (1992), Предложение 4.1.
^ Хит и Розенберг (1992), Предложения 4.2 и 4.3.
^ Хит, Лейтон и Розенберг (1992); Ренгараджан и Вени Мадхаван (1995).
^ Ренгараджан и Вени Мадхаван (1995).
^ Алам и др. (2020).
^ Хит и Розенберг (1992), Предложение 4.6.
^ Грегор, Шкрековски и Вукашинович (2012)
^ Хит и Розенберг (1992), Предложения 4.7 и 4.8.
^ Хит и Розенберг (1992), Теорема 3.2.
^ Вуд (2005).
^ Хит и Розенберг (1992), Теорема 3.6
^ ab Дуймович и Вуд (2004).
^ Хит, Лейтон и Розенберг (1992). Полиномиальный алгоритм для поиска макета с близким к этому числу очередей предложен Шахрохи и Ши (2000). Дуймович и Вуд (2004) улучшили постоянный множитель в этой связи до ⁠ ⁠ $e{\sqrt {м}}$ , где $e$ — основание натурального логарифма .
^ Хит, Лейтон и Розенберг (1992); Вуд (2008).
^ ab Дуймович и др. (2022)
^ ab Хит, Лейтон и Розенберг (1992).
^ Дуймович и Вуд (2005).
^ Dujmović & Wood (2003); Dujmović, Morin & Wood (2005). См. Wood (2002) для более слабого предварительного результата, ограничивающего число очередей шириной пути или комбинацией ширины дерева и степени.
^ Хит и Розенберг (1992), Следствие 3.9.
^ Хит и Розенберг (1992), Теорема 2.3.
^ Нешетржил, Оссона де Мендес и Вуд (2012); Нешетржил и Оссона де Мендес (2012), стр. 321–327.
^ Нешетржил и Оссона де Мендес (2012), Теорема 18.2, с. 401.
^ Wood (2002); Dujmović, Pór & Wood (2004); Dujmović, Morin & Wood (2005). См. Di Giacomo & Meijer (2004) для более точных границ размеров сетки для графиков с малым числом очередей.
^ Дуймович и Вуд (2003)
^ Дуймович, Морен и Вуд (2005)
^ Дуймович и др. (2020)

Ссылки

Auer, Christopher; Bachmaier, Christian; Brandenburg, Franz Josef; Brunner, Wolfgang; Gleißner, Andreas (2011), "Plane drawings of queue and deque graphs", Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21–24, 2010, Revised Selected Papers , Lecture Notes in Computer Science, vol. 6502, Heidelberg: Springer, pp. 68–79, doi : 10.1007/978-3-642-18469-7_7 , ISBN 978-3-642-18468-0, г-н 2781254.
Алам, Джавахерул Мд.; Бекос, Майкл А.; Гронеманн, Мартин; Кауфманн, Майкл; Пупырев, Сергей (2020), «Очередь макетов плоских 3-деревьев», Algorithmica , 9 (82): 2564–2585, arXiv : 1808.10841 , doi : 10.1007/s00453-020-00697-4, S2CID 52143414.
Бекос, Майкл А.; Гронеманн, Мартин; Рафтопулу, Хрисанти Н. (2021), «О числе очередей планарных графов», Рисование графов: 29-й международный симпозиум, GD 2021, Тюбинген, Германия, 14–17 сентября 2021 г., Пересмотренные избранные статьи , Конспект лекций по информатике, Гейдельберг: Springer.
Ди Баттиста, Джузеппе; Фрати, Фабрицио; Пах, Янош (2013), «О количестве очередей плоских графов» (PDF) , SIAM Journal on Computing , 42 (6): 2243–2285, doi : 10.1137/130908051, MR 3141759.
Di Giacomo, Emilio; Meijer, Henk (2004), «Рисунок траектории графов с постоянным номером очереди», Graph Drawing: 11th International Symposium, GD 2003 Perugia, Italy, September 21–24, 2003 Revised Papers , Lecture Notes in Computer Science, vol. 2912, Berlin: Springer, pp. 214–225, doi : 10.1007/978-3-540-24595-7_20 , ISBN 978-3-540-20831-0, г-н 2177595.
Дуймович, Вида (2015), «Графовые макеты с помощью многослойных сепараторов», Журнал комбинаторной теории , Серия B, 110 : 79–89, arXiv : 1302.0304 , doi : 10.1016/j.jctb.2014.07.005, MR 3279388, S2CID 60212.
Дуймович, Вида ; Эппштейн, Дэвид ; Хикингботам, Роберт; Морин, Пэт ; Вуд, Дэвид Р. (2022), «Число стека не ограничено числом очереди», Combinatorica , 42 (2): 151–164, arXiv : 2011.04195 , doi : 10.1007/s00493-021-4585-7, MR 4426297, S2CID 226281691.
Дуймович, Вида ; Джорет, Гвенэль; Мичек, Петр; Морен, Пэт ; Юкердт, Торстен; Вуд, Дэвид Р. (2020), «Плоские графы имеют ограниченный номер очереди», Журнал ACM , 67 (4): 1–38, arXiv : 1904.04791 , doi : 10.1145/3385731
Дуймович, Вида ; Морин, Пэт ; Вуд, Дэвид Р. (2005), «Размещение графов с ограниченной шириной дерева», SIAM Journal on Computing , 34 (3): 553–579, arXiv : cs/0406024 , doi :10.1137/S0097539702416141, MR 2137079, S2CID 3264071.
Дуймович, Вида ; Морин, Пэт ; Вуд, Дэвид Р. (2013), «Слоистые разделители для макетов очередей, рисования трехмерных графов и неповторяющейся раскраски», Труды 54-го симпозиума IEEE по основам компьютерной науки (FOCS '13) , стр. 280–289, arXiv : 1306.1595 , doi : 10.1109/FOCS.2013.38, ISBN 978-0-7695-5135-7, S2CID 5613857.
Дуймович, Вида ; Пор, Аттила; Вуд, Дэвид Р. (2004), «Трековые макеты графов» (PDF) , Дискретная математика и теоретическая информатика , 6 (2): 497–521, arXiv : cs/0407033 , Bibcode : 2004cs........7033D, MR 2180055.
Dujmović, Vida ; Wood, David R. (2003), "Разбиения деревьев k- деревьев с приложениями в компоновке графов", Графовые концепции в информатике: 29-й международный семинар, WG 2003. Elspeet, Нидерланды, 19-21 июня 2003 г. Revised Papers , Lecture Notes in Computer Science, т. 2880, Berlin: Springer, стр. 205–217, CiteSeerX 10.1.1.130.1914 , doi :10.1007/978-3-540-39890-5_18, ISBN 978-3-540-20452-7, МР 2080081.
Дуймович, Вида ; Вуд, Дэвид Р. (2004), «О линейных схемах графов» (PDF) , Дискретная математика и теоретическая информатика , 6 (2): 339–357, MR 2081479.
Дуймович, Вида ; Вуд, Дэвид Р. (2005), «Стеки, очереди и дорожки: макеты подразделений графа» (PDF) , Дискретная математика и теоретическая информатика , 7 (1): 155–201, doi :10.46298/dmtcs.346, MR 2164064.
Ganley, Joseph L.; Heath, Lenwood S. (2001), "The pagenumber of k -trees is O ( k )", Discrete Applied Mathematics , 109 (3): 215–221, doi : 10.1016/S0166-218X(00)00178-5 , MR 1818238.
Грегор, Петр; Шкрековски, Ристе; Вукашинович, Вида (2011), «О числе очередей гиперкуба», Электронные заметки по дискретной математике , 38 : 413–418, doi :10.1016/j.endm.2011.09.067.
Грегор, Петр; Шкрековски, Ристе; Вукашинович, Вида (2012), «Схемы очередей гиперкубов», SIAM Journal on Discrete Mathematics , 26 (1): 77–88, CiteSeerX 10.1.1.417.7129 , doi : 10.1137/100813865.
Хасунума, Тору; Хирота, Миса (2007), «Улучшенная верхняя граница числа очередей гиперкуба», Information Processing Letters , 104 (2): 41–44, doi :10.1016/j.ipl.2007.05.006, MR 2343263.
Хит, Ленвуд С.; Лейтон, Фрэнк Томсон ; Розенберг, Арнольд Л. (1992), «Сравнение очередей и стеков как механизмов для компоновки графов», SIAM Journal on Discrete Mathematics , 5 (3): 398–412, doi :10.1137/0405031, MR 1172748.
Хит, Ленвуд С.; Розенберг, Арнольд Л. (1992), «Размещение графов с использованием очередей», SIAM Journal on Computing , 21 (5): 927–958, doi :10.1137/0221055, MR 1181408.
Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, т. 28, Springer, doi : 10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, МР 2920058.
Нешетржил, Ярослав ; Оссона де Мендес, Патрис ; Вуд, Дэвид Р. (2012), «Характеристики и примеры классов графов с ограниченным расширением», Европейский журнал комбинаторики , 33 (3): 350–373, arXiv : 0902.3265 , doi : 10.1016/j.ejc.2011.09.008, MR 2864421, S2CID 2633083.
Пай, Кунг-Жуй; Чанг, Джоу-Мин; Ван, Юэ-Ли (2008), «Заметка о «Улучшенной верхней границе числа очередей гиперкуба»", Письма по обработке информации , 108 (3): 107–109, doi :10.1016/j.ipl.2008.04.019, MR 2452135.
Rengarajan, S.; Veni Madhavan, CE (1995), "Стек и число очередей 2-деревьев", Computing and Combinatorics: First Annual International Conference, COCOON '95 Сиань, Китай, 24–26 августа 1995 г., Труды , Lecture Notes in Computer Science, т. 959, Берлин: Springer, стр. 203–212, doi :10.1007/BFb0030834, ISBN 978-3-540-60216-3, МР 1450116.
Шахрохи, Фархад; Ши, Вэйпин (2000), «О пересекающихся множествах, непересекающихся множествах и номере страницы», Журнал алгоритмов , 34 (1): 40–53, doi :10.1006/jagm.1999.1049, MR 1732197.
Wood, David R. (2002), «Разметка очередей, ширина дерева и трехмерное рисование графов», FST TCS 2002: Основы программных технологий и теоретической информатики, 22-я конференция Канпур, Индия, 12–14 декабря 2002 г., Труды , Lecture Notes in Computer Science, т. 2556, Берлин: Springer, стр. 348–359, doi :10.1007/3-540-36206-1_31, ISBN 978-3-540-00225-3, МР 2046017.
Вуд, Дэвид Р. (2005), «Очередь макетов графовых произведений и степеней» (PDF) , Дискретная математика и теоретическая информатика , 7 (1): 255–268, doi :10.46298/dmtcs.352, MR 2183176, S2CID 2361133.
Вуд, Дэвид Р. (2008), «Графы ограниченной степени имеют произвольно большое число очередей», Дискретная математика и теоретическая информатика , 10 (1): 27–34, arXiv : math/0601293 , Bibcode : 2006math......1293W.

Внешние ссылки

Макеты стека и очереди, проблемы, представленные летом 2009 г., исследовательский опыт для аспирантов, Дуглас Б. Уэст