Это хорошая статья. Для получения дополнительной информации нажмите здесь.
Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Трехстраничное книжное вложение полного графа K 5 . Поскольку это не планарный граф , его невозможно встроить без пересечений на меньшее количество страниц, поэтому его книжная толщина равна трем.

В теории графов , А книга вложение является обобщением плоского вложения в виде графа с вложениями в книгу , коллекция полуплоскость все имеющие ту же самую линия , как их граница. Обычно вершины графа должны лежать на этой граничной линии, называемой позвоночником , а ребра должны оставаться в одной полуплоскости. Книга толщина графа называется наименьшее возможное количество полуплоскостям для любой книги вложения графа. Толщина книги также называют PageNumber , stacknumber или фиксированной outerthickness. Вложения книг также использовались для определения нескольких других инвариантов графов, включая ширину страницы и число перекрестков.

Каждый граф с n вершинами имеет максимальную толщину книги , и эта формула дает точную толщину книги для полных графов . Графики с толщиной книги 1 являются внешнепланарными графиками . Графы с толщиной книги не более двух - это субгамильтоновы графы , которые всегда плоские ; В более общем смысле, каждый плоский граф имеет толщину книги не более четырех. Все семейства минорно-замкнутых графов , и в частности графы с ограниченной древесной шириной или ограниченным родом , также имеют ограниченную толщину книги. Это NP-сложно для определения точной толщины книги данного графа, зная или не зная фиксированный порядок вершин вдоль корешка книги.

Одна из первоначальных мотиваций для изучения вложений книг была связана с приложениями в проектировании СБИС , в которых вершины вложения книги представляют собой компоненты схемы, а провода представляют собой связи между ними. Встраивание книг также имеет приложения для рисования графиков , где два стандартных стиля визуализации для графиков, дуговых диаграмм и круговых макетов могут быть созданы с использованием вложений книг.

При планировании перевозок различные источники и пункты назначения пешеходов и транспортных средств, которые встречаются и взаимодействуют на светофоре, могут быть смоделированы математически как вершины графа с ребрами, соединяющими разные пары источник-пункт назначения. Книжное вложение этого графика может быть использовано для разработки расписания, которое позволяет всему трафику перемещаться через перекресток с минимально возможным количеством фаз сигнала. В задачах биоинформатики, связанных со сворачивающейся структурой РНК , одностраничные книжные вложения представляют собой классические формы вторичной структуры нуклеиновых кислот , а двухстраничные книжные вложения представляют собой псевдоузлы . Другие применения книжных вложений включают: абстрактная алгебра и теория узлов .

Есть несколько открытых проблем, касающихся толщины книги. Неизвестно, может ли толщина книги произвольного графа быть ограничена функцией толщины книги его подразделов . Проверка существования трехстраничного книжного вложения графа при фиксированном порядке вершин вдоль позвоночника вложения имеет неизвестную вычислительную сложность: не известно, что он разрешим за полиномиальное время, и не известен как NP-сложный. . И хотя каждый плоский граф имеет книжную толщину не более четырех, неизвестно, существует ли планарный граф, книжная толщина которого равна ровно четырем.

История [ править ]

Понятие книги как топологического пространства было определено К.А. Персингером и Гейл Атнеозен в 1960-х годах. [1] [2] В рамках этой работы Атнеозен уже рассматривал вложения графов в своих книгах. Вложения, которые он изучал, использовали то же определение, что и вложения графов в любое другое топологическое пространство: вершины представлены различными точками, ребра представлены кривыми, и единственный способ пересечения двух ребер - это их пересечение в общей конечной точке.

В начале 1970-х годов Пол К. Кайнен и Л. Тейлор Оллманн разработали более ограниченный тип встраивания, который стал использоваться в большинстве последующих исследований. В их формулировке вершины графа должны располагаться вдоль корешка книги, а каждое ребро должно лежать на одной странице. [3] [4] Важные вехи в более позднем развитии книжных вложений включают доказательство Михалиса Яннакакиса в конце 1980-х, что плоские графы имеют книжную толщину не более четырех, [5] [6] и открытие в конце 1990-х близких связь книжных вложений и биоинформатики . [7]

Определения [ править ]

Граф полезности K 3,3 не имеет вложения в 2-страничную книгу, но его можно нарисовать, как показано в 2-страничной книге, только с одним пересечением. Следовательно, его двухстраничный буккроссинг - 1.
Это одностраничное встраивание ромбовидного графа имеет ширину страницы 3, потому что желтый луч пересекает три края.

Книга представляет собой особый вид топологического пространства , также называется вентилятором полуплоскость. [1] [8] Он состоит из одной линии ℓ , называемой корешком или оборотной стороной книги, вместе с набором из одной или нескольких полуплоскостей , называемых страницами или листами книги, [9] каждая из которых имеет позвоночник как его граница. Книги с конечным числом страниц можно встроить в трехмерное пространство, например, выбрав ℓ в качестве оси zДекартова система координат и выбор страниц в качестве k полуплоскостей, двугранный угол которых относительно плоскости xz кратен 2 π / k . [10]

Книга рисования конечного графа G на книжной B является рисунок из G на B таким образом, что каждая вершина G обращается в виде точки на позвоночнике B , и каждое ребро G обращается в качестве кривой , которая лежит в пределах одной страницы B . К -page номер книги переправа из G минимальное число пересечений в К -page книжной графики. [11]

Книга вложения из G на B является книгой рисунок , который образует граф вложения из G в B . То есть это книжный рисунок G на B , который не имеет пересечений ребер. Каждый конечный граф имеет книгу, вложенную в книгу с достаточно большим количеством страниц. Например, всегда можно встроить каждое ребро графа на отдельную страницу. Толщина книги , PageNumber или стек число из G минимального количества страниц , необходимое для книги вложения  G. Еще одним параметром, который измеряет качество встраивания книги, помимо количества страниц, является ее ширина страницы . Это максимальное количество краев, которое может пересечь луч, перпендикулярный корешку в пределах одной страницы. Эквивалентно (для вложений книг, в которых каждое ребро нарисовано как монотонная кривая), это максимальный размер подмножества ребер на одной странице, так что интервалы, определенные на корешке парами конечных точек ребер, пересекаются друг с другом. . [12] [13] [14]

Для этих определений очень важно, чтобы края не выходили за пределы одной страницы книги. Как уже заметил Атнеозен, если вместо этого края могут переходить от одной страницы к другой через корешок книги, то каждый график может быть встроен в трехстраничную книгу. [15] [2] [16] Для такого трехстраничного топологического вложения книги, в котором разрешены пересечения позвоночника, каждый граф может быть вложен с не более чем логарифмическим числом пересечений позвоночника на ребро, [15] и для некоторых графов это необходимо. много перекрестков позвоночника. [17]

Конкретные графики [ править ]

Как показано на первом рисунке, книжная толщина полного графа K 5 равна трем: у неплоского графа его книжная толщина больше двух, но существует вложение книги с тремя страницами. В более общем смысле, книжная толщина каждого полного графа с n ≥ 4 вершинами точно равна . Этот результат также дает верхнюю границу максимально возможной толщины книги любого графа с n вершинами. [10]

Число двухстраничного пересечения полного графа K n равно

соответствие все еще недоказанной гипотезе Энтони Хилла о том, каким должно быть неограниченное число пересечений этого графа. То есть, если гипотеза Хилла верна, то рисунок этого графика, который минимизирует количество пересечений, представляет собой двухстраничный рисунок. [18]

Книжная толщина полного двудольного графа K a , b не превосходит min ( a , b ) . Чтобы построить рисунок с такой толщиной книги, для каждой вершины на меньшей стороне двудольного раздела можно разместить ребра, инцидентные этой вершине, на их собственной странице. Эта граница не всегда жесткая; например, K 4,4 имеет книжную толщину три, а не четыре. Однако, когда две стороны графика очень неуравновешены, когда b > a ( a - 1) , толщина книги K a , b в точности равна a .[10] [19]

Для графа Турана T ( kr , r ) ( полный многодольный граф K k , k , ..., сформированный из r независимых наборов из k вершин на независимый набор, с ребром между каждыми двумя вершинами из разных независимых наборов) толщина книги т зажат между

а когда r нечетно, верхняя граница может быть улучшена до

[10] [20]

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

Свойства [ править ]

Планарность и внешнепланарность [ править ]

Граф Гольднера – Харари , плоский граф с книжной толщиной три

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

Каждое вложение двухстраничной книги является частным случаем плоского вложения, потому что объединение двух страниц книги является пространством, топологически эквивалентным всей плоскости. Следовательно, каждый график с книжной толщиной два автоматически является планарным графом . Точнее, книжная толщина графа G не превосходит двух тогда и только тогда, когда G является подграфом плоского графа, имеющего гамильтонов цикл . [10] Если графу задано двухстраничное вложение, его можно расширить до плоского гамильтонова графа, добавив (на любую страницу) дополнительные ребра между любыми двумя последовательными вершинами вдоль позвоночника, которые еще не являются смежными, и между первыми и последние вершины позвоночника. ВГраф Гольднера – Харари представляет собой пример плоского графа, у которого нет книжной толщины два: это максимальный планарный граф , поэтому невозможно добавить к нему какие-либо ребра при сохранении планарности, и он не имеет гамильтонова цикла. [10] Из-за этой характеризации гамильтоновыми циклами графы, в которые вложены книги на две страницы, также известны как субгамильтоновы графы . [12]

Все плоские графы, максимальная степень которых не превышает четырех, имеют толщину книги не более двух. [22] Плоские 3-деревья имеют книжную толщину не более трех. [23] В общем, все плоские графы имеют книжную толщину четыре. [5] [6] [24] Михалис Яннакакис утверждал в 1986 году [6], что существуют некоторые плоские графы, толщина книги которых равна ровно четырем. Однако подробное доказательство этого утверждения, объявленное в последующей журнальной статье [5], было известно только в 2020 году, когда Bekos et al. В [24] представлены плоские графы с шириной дерева 4, требующие четырех страниц в любом вложении книги.

Поведение в подразделениях [ править ]

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

Может ли толщина книги графа быть ограничена сверху функцией толщины книги его подразделения?

(больше нерешенных задач по математике)
Толщина книги ромбовидного графа увеличивается после разделения краев.

Разделение каждого ребра графа на пути с двумя ребрами путем добавления новых вершин внутри каждого ребра может иногда увеличивать его толщину книги. Например, ромбовидный граф имеет книжную толщину один (он внешнепланарный), но его подразделение имеет книжную толщину два (оно плоское и субгамильтоново, но не внешнепланарное). Однако этот процесс подразделения также может иногда значительно уменьшить толщину книги разбитого графа. Например, книжная толщина полного графа K n пропорциональна количеству его вершин, но разделение каждого из его ребер на двухреберный путь приводит только к тому, что толщина книги намного меньше . [25] Несмотря на существование таких примеров, как этот,Бланкеншип и Опоровски (1999) предположили, что толщина книги подразделения не может быть намного меньше, чем у исходного графика. В частности, они предположили, что существует функция f такая, что для каждого графа G и для графа H, образованного заменой каждого ребра в G на двухреберный путь, если толщина книги H равна t, то толщина книги G не превосходит f ( t ) . [16] По состоянию на 2013 год гипотеза Бланкеншипа – Опоровского остается недоказанной. [26]

Связь с другими инвариантами графа [ править ]

Толщина книги связана с толщиной , количеством плоских графов, необходимых для покрытия краев данного графа. Граф G имеет толщину & thetas , если оно может быть обращено в плоскости, а ее края окрашены с & thetas цветов, таким образом , что ребра одного и того же цвета, что и друг с другом не пересекаются. Аналогично, граф G имеет книжную толщину θ, если его можно нарисовать в полуплоскости с вершинами на границе полуплоскости и краями, окрашенными в θ.цвета без пересечения двух краев одного цвета. В этой формулировке толщины книги цвета краев соответствуют страницам вложения книги. Тем не менее, толщина и толщина книга может быть очень отличаются друг от друга: существуют графы ( подразделения из полных графов ) , которые имеют неограниченную толщину книги, [25] [15] [16] , несмотря на толщину двух. [25]

Графы с шириной дерева k имеют книжную толщину не более k + 1 [27] [28], и эта граница точна при k > 2 . [27] Графы с m ребрами имеют книжную толщину , [29] а графы рода g имеют книжную толщину . [30] В более общем смысле, каждое семейство минорных замкнутых графов имеет ограниченную толщину книги. [31] [32] С другой стороны, 1-плоские графы , которые не замкнуты относительно миноров, [31] также имеют ограниченную книжную толщину, [33] но некоторые 1-плоские графы, включая K 2,2,2,2, имеют толщину книги не менее четырех. [34]

Каждый мелкий минор графа ограниченной книжной толщины является разреженным графом , у которого отношение ребер к вершинам ограничено константой, которая зависит только от глубины второстепенного и от толщины книги. То есть, в терминологии Nešetřil & Ossona de Mendez (2012) , графики ограниченной толщины книги имеют ограниченное расширение . [31] Однако даже графы ограниченной степени , гораздо более сильное требование, чем ограниченное расширение, могут иметь неограниченную книжную толщину. [35]

Поскольку графы книжной толщины два являются плоскими графами, они подчиняются теореме о плоском разделителе : у них есть разделители, подмножества вершин, удаление которых разбивает граф на части с не более чем 2 n / 3 вершинами каждый, с только вершинами в разделителе. Здесь n означает количество вершин в графе. Однако существуют графики книжной толщины три, не имеющие разделителей сублинейного размера. [36]

Края в пределах одной страницы встраиваемой книги ведут себя в некотором роде как структура данных стека . Это можно формализовать, рассматривая произвольную последовательность операций push и pop на стеке и формируя граф, в котором операции над стеком соответствуют вершинам графа, размещенным в порядке последовательности вдоль корешка вложения книги. Затем, если нарисовать границу от каждой операции выталкивания, которая выталкивает объект x из стека, к предыдущей операции выталкивания, которая подтолкнула x , результирующий граф автоматически будет иметь одностраничное встраивание. По этой причине номер страницы графика также называют номером его стека . Таким же образом можно рассматривать произвольную последовательность операций постановки и удаления из очереди.структура данных очереди и сформировать граф, вершинами которого являются эти операции, расположенные по порядку на корешке одной страницы, с границей между каждой операцией постановки в очередь и соответствующей постановкой из очереди. Тогда в этом графе каждые два ребра будут либо пересекать, либо покрывать непересекающиеся интервалы на позвоночнике. По аналогии исследователи определили вложение графа в очередь как вложение в топологическую книгу так, что каждая вершина лежит на корешке, каждое ребро лежит на одной странице, а каждые два ребра на одной странице либо пересекаются, либо покрывают непересекающиеся. интервалы на позвоночнике. Минимальное количество страниц, необходимое для встраивания графа в очередь, называется его номером очереди . [31] [37] [38]

Вычислительная сложность [ править ]

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

Найти книжную толщину графика NP-сложно . Это следует из того факта, что нахождение гамильтоновых циклов в максимальных планарных графах является NP-полным . В максимальном плоском графе толщина книги равна двум, если и только если существует гамильтонов цикл. Следовательно, также NP-полно проверить, равна ли книжная толщина данного максимального плоского графа двум. [39]

Если порядок вершин графа вдоль позвоночника вложения фиксирован, то двухстраничное вложение (если оно существует) может быть найдено за линейное время , как пример проверки планарности для графа, образованного путем увеличения заданного граф с циклом, соединяющим вершины в их позвоночном порядке. [7] Унгер (1992) утверждал, что нахождение трехстраничных вложений с фиксированным порядком корешка также может быть выполнено за полиномиальное время, хотя его описание этого результата опускает многие детали. [40] Однако для графов, требующих четырех или более страниц, проблема нахождения вложения с минимально возможным количеством страниц остается NP-трудной благодаря эквивалентности NP-трудной проблеме раскраски. круг графов , то пересечение графов из хорд одного круга . Учитывая график G с упорядочением фиксированного позвоночника для его вершин, используя эти вершины в том же порядке по окружности и рисунок края G в виде отрезков , производит набор аккордов , представляющих G . Затем можно сформировать круговой граф, в котором хорды этой диаграммы являются вершинами, а пары пересекающихся хорд - ребрами. Раскраска кругового графа представляет собой разбиение ребер графа Gна подмножества, которые можно нарисовать без пересечения на одной странице. Следовательно, оптимальная раскраска эквивалентна оптимальному вложению книги. Поскольку раскраска кругового графа в четыре или более цветов является NP-трудной, и поскольку любой круговой граф может быть сформирован таким образом из некоторой задачи вложения книг, то оптимальное вложение книги также является NP-трудным. [41] [42] [43] Для фиксированного порядка вершин на корешке двухстраничного книжного рисунка также NP-сложно минимизировать количество пересечений, когда это число не равно нулю. [42]

Если порядок корешков неизвестен, но дано разделение краев на две страницы, то можно найти вложение 2 страниц (если оно существует) за линейное время с помощью алгоритма, основанного на деревьях SPQR . [44] [45] Тем не менее, найти 2-страничное вложение является NP-полным, когда не известны ни порядок корешков, ни разделение ребер. Нахождение числа перекрестков графа также является NP-трудной задачей из-за NP-полноты специального случая проверки того, является ли число перекрестков на двух страницах равным нулю.

Как следствие ограниченного расширения, проблема изоморфизма подграфов, заключающаяся в том, чтобы определить, существует ли граф-паттерн ограниченного размера как подграф большего графа, может быть решена за линейное время, когда больший граф имеет ограниченную толщину книги. То же самое верно для определения того, является ли граф паттернов индуцированным подграфом большего графа или он имеет гомоморфизм графа к большему графу. [46] [47] По той же причине, проблема тестирования ли толщина подчиняется данная формула график ограниченной книги логики первого порядка является фиксированным параметром послушной . [48]

Bekos, Kaufmann & Zielke (2015) описывают систему для поиска оптимальных вложений книг путем преобразования проблемы в пример проблемы булевой выполнимости и применения SAT-решателя к полученной проблеме. Они заявляют, что их система способна найти оптимальное вложение для максимальных плоских графов с 400 вершинами примерно за 20 минут. [34]

Приложения [ править ]

Отказоустойчивая многопроцессорная обработка [ править ]

Одна из основных причин для изучения встраивания книг, указанная Чангом, Лейтон и Розенбергом (1987), связана с применением в проектировании СБИС для организации отказоустойчивых мультипроцессоров . В системе DIOGENES, разработанной этими авторами, процессоры многопроцессорной системы выстроены в логическую последовательность, соответствующую корешку книги (хотя эта последовательность не обязательно может быть размещена вдоль линии в физическом плане этой системы). Каналы связи, соединяющие эти процессоры, сгруппированы в «связки», которые соответствуют страницам книги и действуют как стопки.: подключение одного из процессоров к началу нового канала связи толкает все предыдущие ссылки вверх в связке, а подключение другого процессора к концу канала связи подключает его к тому, что находится внизу связки, и выталкивает все другие вниз. Из-за такого поведения стека один пакет может обрабатывать набор коммуникационных ссылок, которые образуют края одной страницы при вложении книги. Организуя связи таким образом, можно реализовать большое количество различных топологий сети, независимо от того, какие процессоры вышли из строя, пока остается достаточное количество исправных процессоров для реализации сети. Сетевая топология, которая может быть реализована с помощью этой системы, - это именно те топологии, толщина книги которых не больше, чем количество пакетов, которые были сделаны доступными.[39] Встраивание книги может также использоваться для моделирования размещения проводов, соединяющих компоненты СБИС в слоях схемы. [49]

Сортировка стека [ править ]

Другое приложение, процитированное Чангом, Лейтон и Розенбергом (1987), касается сортировки перестановок с использованием стеков . Влиятельный результат Дональда Кнута  ( 1968 ) показал, что система, которая обрабатывает поток данных , помещая входящие элементы в стек, а затем, в надлежащим образом выбранное время, выталкивает их из стека в выходной поток, может сортировать данные тогда и только тогда, когда его начальный порядок описывается перестановкой, которая избегает шаблона перестановки 231. [50]С тех пор было много работы над аналогичными проблемами сортировки потоков данных по более общим системам стеков и очередей. В системе, рассмотренной Чангом, Лейтон и Розенбергом (1987) , каждый элемент из потока входных данных должен быть помещен в один из нескольких стеков. Затем, как только все данные были помещены таким образом, элементы выталкиваются из этих стеков (в соответствующем порядке) в выходной поток. Как Chung et al. Заметьте, данная перестановка может быть отсортирована этой системой тогда и только тогда, когда определенный граф, полученный из перестановки, имеет вложение книги с вершинами в определенном фиксированном порядке вдоль корешка и с числом страниц, которое не более чем равно к количеству стопок. [39]

Управление движением [ править ]

Транспортная развязка. Четыре входящие и четыре исходящие пары проходных полос, два кармана поворота и четыре угла пешеходного перехода могут быть представлены как набор из 14 вершин на корешке книжного вложения, с ребрами, представляющими связи между этими точками.

Как описал Кайнен (1990) , вложение книги может использоваться для описания фаз светофора.на контролируемом перекрестке. На перекрестке входящие и исходящие полосы движения (включая концы пешеходных переходов и велосипедных дорожек, а также полосы для транспортных средств) могут быть представлены в виде вершин графа, помещенного на корешок книги, вложенной в них по часовой стрелке. порядок вокруг перекрестка. Пути через перекресток, по которым движется транспортный поток для перехода от входящей полосы к исходящей полосе, могут быть представлены как края неориентированного графа. Например, этот график может иметь ребро от входящей полосы движения к исходящей, которые оба принадлежат одному и тому же сегменту дороги, представляя разворот от этого сегмента обратно к этому сегменту, только если развороты разрешены на данном участке дороги. соединение. Для данного подмножества этих ребер подмножество представляет собой набор путей, по которым можно пройти без взаимного вмешательства, если и только если это подмножество не включает ни одной пары ребер, которые пересекались бы, если бы эти два ребра были помещены на одну страницу вложения книги. Таким образом, книжное вложение этого графа описывает разделение путей на не мешающие подмножества, а книжная толщина этого графа (с его фиксированным вложением на корешок) дает минимальное количество различных фаз, необходимых для расписания сигнализации, которое включает все возможные пути движения через развязку.[51]

Рисование графика [ править ]

Дуги диаграмма , на графике Голднера-Харарях . Чтобы создать плоскую диаграмму, два треугольника графа были разделены на четыре пунктирной красной линией, в результате чего одно из ребер графа продолжалось как выше, так и ниже линии.

Встраивание книг также часто применяется при визуализации сетевых данных. Два из стандартных макетов при рисовании графов , дуговые диаграммы [52] и круговые макеты, [53] можно рассматривать как вложения книг, а встраивание книг также применялось при построении кластерных макетов, [44] одновременных вложений, [54] ] и трехмерные графические рисунки. [55]

Дуги диаграмма , [52] или линейное вложение [42] мест вершин графа вдоль линии, и рисует края графика , как полукругов выше или ниже этой линии, иногда также позволяя кромки быть обращено на сегменты линии. Этот стиль рисования соответствует встраиванию книги либо с одной страницей (если все полукруги над линией), либо с двумя страницами (если используются обе стороны линии), и первоначально был введен как способ изучения количества пересечений графиков. [56] [57]Плоские графы, в которых нет двухстраничных книжных вложений, также можно рисовать аналогичным образом, позволяя представлять их края в виде нескольких полукругов над и под линией. Такой рисунок не является вложением книги по обычному определению, но был назван топологическим вложением книги . [58] Для каждого плоского графа всегда можно найти такое вложение, в котором каждое ребро пересекает спайн не более одного раза. [59]

Круговая схема графа Хваталь

В другом стиле рисования, круговой компоновке , вершины графа помещаются в круг, а края рисуются либо внутри, либо за пределами круга. [53] Опять же, размещение краев внутри круга (например, как сегменты прямой линии) соответствует рисунку книги на одной странице, в то время как размещение внутри и снаружи круга соответствует рисунку книги на двух страницах. [60]

Для одностраничных рисунков любого стиля важно, чтобы количество пересечений было небольшим, чтобы уменьшить визуальный беспорядок на рисунке. Сведение к минимуму количества пересечений NP-полной , [42] , но может быть аппроксимирована с соотношением аппроксимации O (войти 2  п ) , где п есть число вершин. [61] Минимизация числа пересечений на одной или двух страницах является управляемым с фиксированным параметром, если параметризовано цикломатическим номером данного графа или комбинацией числа пересечений и ширины дерева графа. [62] [63]Также были разработаны эвристические методы для уменьшения сложности пересечения, основанные, например, на тщательном порядке вставки вершин и на локальной оптимизации . [53]

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

Книжные вложения с более чем двумя страницами также использовались для построения трехмерных чертежей графиков. В частности, Вуд (2002) использовал конструкцию для встраивания книг, которая поддерживает низкую степень каждой вершины на каждой странице, как часть метода встраивания графов в трехмерную сетку небольшого объема. [55]

Сворачивание РНК [ править ]

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

При изучении того, как молекулы РНК складываются, образуя свою структуру, стандартная форма вторичной структуры нуклеиновой кислоты может быть схематически описана как цепочка оснований (сама последовательность РНК), проведенная вдоль линии вместе с набором дуг над ней. линия, описывающая пары оснований конструкции. То есть, хотя эти структуры на самом деле имеют сложную трехмерную форму, их связь (когда существует вторичная структура) может быть описана более абстрактной структурой, встраиванием одностраничной книги. Однако не все складки РНК ведут себя так просто. Haslinger & Stadler (1999) предложили так называемую «двухвторичную структуру» для некоторых псевдоузлов РНК.это принимает форму вложения двухстраничной книги: последовательность РНК снова рисуется вдоль линии, но пары оснований изображаются в виде дуг как над, так и под этой линией. Чтобы сформировать двухвторичную структуру, граф должен иметь максимальную степень не более трех: каждая база может участвовать только в одной дуге диаграммы в дополнение к двум ссылкам на своих соседей в базовой последовательности. Преимущества этой формулировки включают тот факт, что она исключает структуры, которые фактически связаны в пространстве, и что она соответствует большинству известных псевдоузлов РНК. [7]

Поскольку для этого приложения порядок шипов известен заранее, проверка существования двухвторичной структуры для данной пары оснований не вызывает затруднений. Проблема присвоения краев к двум страницам совместимым способа может быть приготовлена в виде любого экземпляра 2-выполнимости , или как проблема тестирования bipartiteness в окружности графа , вершины которого являются парами оснований , а ребра описывают переходы между парами оснований. [7] Альтернативно и более эффективно, как показывают Haslinger & Stadler (1999) , двухвторичная структура существует тогда и только тогда, когда диаграмма графавходных данных (граф, образованный соединением оснований в цикл в порядке их последовательности и добавлением заданных пар оснований в качестве ребер) является плоским графом . [7] Эта характеристика позволяет распознать двухвторичные структуры за линейное время как пример проверки планарности .

Blin et al. (2007) использовали связь между вторичными структурами и вложениями книг как часть доказательства NP- сложности некоторых проблем при сравнении вторичных структур РНК. [64] И если структура РНК является третичной, а не двухвторичной (то есть, если для нее требуется более двух страниц на диаграмме), то определение номера страницы снова является NP-трудным. [65]

Теория вычислительной сложности [ править ]

Паван, Тевари & Vinodchandran (2012) подержанная книга вложения для изучения теории сложности вычислений в достижимости задачи в ориентированных графах . Как они заметили, достижимость для двухстраничных ориентированных графов может быть решена в однозначном логарифмическом пространстве (аналог для логарифмической пространственной сложности класса UP однозначных задач с полиномиальным временем). Однако достижимость трехстраничных ориентированных графов требует полной мощности недетерминированного логарифмического пространства . Таким образом, книжные вложения кажутся тесно связанными с различием между этими двумя классами сложности. [66]

Существование расширяющих графов с постоянным номером страницы [36] является ключевым шагом в доказательстве того, что не существует субквадратного времени моделирования двухленточных недетерминированных машин Тьюринга однопленочными недетерминированными машинами Тьюринга. [67]

Другие области математики [ править ]

McKenzie & Overbay (2010) изучают приложения толщины книги в абстрактной алгебре , используя графы, определенные из делителей нуля конечного локального кольца , создавая вершину для каждого делителя нуля и ребро для каждой пары значений, произведение которых равно нулю. [68]

В последовательности из нескольких статей Дынников изучил топологические книжные вложения узлов и звеньев , показав, что эти вложения могут быть описаны комбинаторной последовательностью символов и что топологическая эквивалентность двух звеньев может быть продемонстрирована последовательностью локальных изменений в вложения. [69] [70]

Ссылки [ править ]

  1. ^ Б Персингер, CA (1966), "Подмножества п -books в Е 3 ", Тихоокеанский журнал математики , 18 : 169-173, DOI : 10,2140 / pjm.1966.18.169 , МР  0195077.
  2. ^ a b Атнеозен, Гейл Адель (1968), О вложимости компактов в n -книги: внутренние и внешние свойства , Ph.D. диссертация, Университет штата Мичиган , стр. 79, Руководство по ремонту 2617705 . Смотрите также Atneosen, Gail H. (1972), "Одномерный п -leaved континуумов" (PDF) , Fundamenta Mathematicae , 74 (1): 43-45 DOI : 10,4064 / фм-74-1-43-45 , Руководство по ремонту 0293592  .
  3. ^ Кайнен, Пол К. (1974), «Некоторые недавние результаты в топологической теории графов», в Бари, Рут А.; Харари, Франк (ред.), Графы и комбинаторика (Труды конференции Capital по теории графов и комбинаторике в Университете Джорджа Вашингтона 18–22 июня 1973 г.) , Lecture Notes in Mathematics, 406 , pp. 76–108.
  4. ^ Оллманн, Л. Тейлор (1973), «О книжных толщинах различных графов», у Хоффмана, Фредерика; Левоу, Рой Б.; Томас, Роберт С.Д. (ред.), Proc. 4-я Юго-Восточная конференция по комбинаторике, теории графов и вычислениям , Congressus Numerantium, VIII , p. 459.
  5. ^ a b c Яннакакис, Михалис (1989), «Вложение плоских графов на четыре страницы», Журнал компьютерных и системных наук , 38 : 36–67, DOI : 10.1016 / 0022-0000 (89) 90032-9
  6. ^ a b c Яннакакис, Михалис (1986), «Четыре страницы необходимы и достаточны для плоских графов», Труды 18-го симпозиума ACM по теории вычислений (STOC '86) , стр. 104–108, DOI : 10.1145 / 12130.12141 , ISBN 0-89791-193-8, S2CID  5359519.
  7. ^ a b c d e Хаслингер, Кристиан; Стадлер, Питер Ф. (1999), "РНК - структуры с псевдо-узлами: График теоретико-, комбинаторными и статистическими свойствами", Бюллетень математической биологии , 61 (3): 437-467, DOI : 10,1006 / bulm.1998.0085 , PMC 7197269 , PMID 17883226  .
  8. ^ Хейлза, ТЦ (1997), "Сфера упаковки II.", Дискретные и Вычислительная геометрия , 18 (2): 135-149, DOI : 10.1007 / PL00009312 , МР 1455511 .
  9. ^ Терминология «позвоночник» и «страницы» является более стандартной в современных теоретико-графических подходах к предмету. О терминологии «спина» и «листья» см. Persinger (1966) .
  10. ^ a b c d e f g Бернхарт, Фрэнк Р .; Кайнен, Пол К. (1979), "Толщина книги графа", Журнал комбинаторной теории , серия B, 27 (3): 320–331, DOI : 10.1016 / 0095-8956 (79) 90021-2 , MR 0554297 .
  11. ^ Шахрохи, Фархад; Секели, Ласло А .; Сикора, Ондрей; Vrťo, Имрих (1996), "Книга пересечения число графа", Журнал теории графов , 21 (4): 413-424, DOI : 10.1002 / (SICI) 1097-0118 (199604) 21: 4 <413: : AID-JGT7> 3.3.CO; 2-5 , MR 1377615 .
  12. ^ Б с Heath, Lenwood S. (1987 г.), "Вложение Внешнепланарные графов в небольших книгах", SIAM Journal на алгебраических и дискретных методов , 8 (2): 198-218, DOI : 10,1137 / 0608018 , МР 0881181 .
  13. ^ Stöhr, Елена (1988), "Компромисс между номером страницы и шириной страницы встраивания графиков книги", Информация и вычисления , 79 (2): 155–162, DOI : 10.1016 / 0890-5401 (88) 90036 -3 , Руководство по ремонту 0968104 .
  14. ^ Stöhr, Елена (1991), "Ширина страницы трехвалентных плоских графов", Дискретная математика , 89 (1): 43–49, DOI : 10.1016 / 0012-365X (91) 90398-L , MR 1108073 .
  15. ^ a b c Эномото, Хико; Мияучи, Мики Симабара (1999), «Вложение графов в трехстраничную книгу с O ( M log N ) пересечений ребер над позвоночником», SIAM Journal on Discrete Mathematics , 12 (3): 337–341, doi : 10.1137 / S0895480195280319 , Руководство по ремонту 1710241 .
  16. ^ a b c Бланкеншип, Робин; Опоровски, Богдан (1999), Рисование подразделов полных и полных двудольных графов на книгах , Технический отчет 1999-4, Департамент математики, Университет штата Луизиана, CiteSeerX 10.1.1.36.4358 .
  17. ^ Эномото, Хико; Мияути, Мики Симабара; Ота, Katsuhiro (1999), «Нижние оценки для числа ребер-переходов через позвоночник в топологической книге вложения графа», Дискретная прикладная математика , 92 (2-3): 149-155, DOI : 10.1016 / S0166 -218X (99) 00044-X , Руководство по ремонту 1697548 .
  18. ^ Ábrego, Бернардо М .; Айххольцер, Освин; Фернандес-Мерчант, Сильвия; Рамос, Педро; Салазар, Геласио (2012), «2-страничное число пересекающихся K n (расширенное резюме)», Труды 28-го ежегодного симпозиума по вычислительной геометрии (SCG'12) , ACM, Нью-Йорк, стр. 397–403, doi : 10.1145 / 2261250.2261310 , Руководство по ремонту 3050657 , S2CID 8344088  .
  19. ^ Дополнительные результаты о толщине книги полных двудольных графов см. В Enomoto, Hikoe; Накамигава, Томоки; Ота, Katsuhiro (1997), "О PageNumber полных графов двудольных" Журнал комбинаторной теории , Series B, 71 () 1: 111-120, DOI : 10,1006 / jctb.1997.1773 , MR 1469870 ; де Клерк, Этьен; Пасечник, Дмитрий В .; Салазар, Геласио (2014), «Книжные рисунки полных двудольных графов», Дискретная прикладная математика , 167 : 80–93, arXiv : 1210.2918 , doi : 10.1016 / j.dam.2013.11.001 , MR 3166108 , S2CID 40920263  .
  20. ^ Sperfeld, Конрад (2013), "На странице числа полных нечетных дольных графов", дискретная математика , 313 (17): 1689-1696, DOI : 10.1016 / j.disc.2013.04.028 , МР 3061004 .
  21. ^ Хасунума, Тору; Shibata, Юкио (1997), "Погружение де Брейна, Kautz и Shuffle-обменные сети в книгах", дискретная Прикладная математика , 78 (1-3): 103-116, DOI : 10.1016 / S0166-218X (97) 00009-7 , MR 1475820 ; Танака, Юки; Shibata, Юкио (2010), "О PageNumber из куба соединенных циклов", Математика в области компьютерных наук , 3 (1): 109-117, DOI : 10.1007 / s11786-009-0012-у , MR 2596254 , S2CID 11830437  . Смотрите также Obrenić, Бояна (1993), "Погружение де Брейна и перетасовать-обменные графики в пять страниц", SIAM журнал по дискретной математике , 6 (4): 642-654, DOI : 10,1137 / 0406049 , MR 1241401 .
  22. ^ Бекос, Майкл А .; Гронеманн, Мартин; Рафтопулу, Хрисанти Н. (2014), «Двухстраничные книжные вложения 4-плоских графов», Труды 31-го симпозиума по теоретическим аспектам информатики , стр. 137–148, arXiv : 1401.0684 , doi : 10.4230 / LIPIcs. STACS.2014.137.
  23. ^ Хит, Ленни (1984), «Вложение плоских графов на семи страницах», Труды 25-го ежегодного симпозиума по основам компьютерных наук , стр. 74–83, DOI : 10.1109 / SFCS.1984.715903.
  24. ^ a b Бекос, Майкл А .; Кауфманн, Майкл; Клют, Фабиан; Пупырев, Сергей; Рафтопулу, Хризанти; Ueckerdt, Torsten (2020), Четыре страницы действительно необходимы для плоских графов , arXiv : 2004.07630.
  25. ^ a b c Эппштейн, Дэвид (2001), Разделение геометрической толщины от толщины книги , arXiv : math.CO/0109195.
  26. ↑ Вуд, Дэвид (19 января 2009 г.), «Толщина книги в подразделах» , Open Problem Garden , получено 5 февраля 2013 г..
  27. ^ а б Дуймович, Вида; Вуд, Дэвид Р. (2007), «Параметры геометрической толщины и ширины графика», Дискретная и вычислительная геометрия , 37 (4): 641–670, arXiv : math / 0503553 , doi : 10.1007 / s00454-007-1318-7 , S2CID 9141367 .
  28. ^ Гэнли, Джозеф L .; Хит, Lenwood С. (2001), "О PageNumber из к -деревьях есть О ( к ) ", Дискретный прикладной математики , 109 (3): 215-221, DOI : 10.1016 / S0166-218X (00) 00178-5 , MR 1818238 .
  29. ^ Malitz, Сет М. (1994), "Графы с Й краями имеют PageNumber O (√ Е ) ", журнал алгоритмы , 17 (1): 71-84, DOI : 10,1006 / jagm.1994.1027 , МР 1279269 .
  30. ^ Malitz, Сет М. (1994), "Genus г графики имеют PageNumber O (√ г ) ", журнал алгоритмов , 17 (1): 85-109, DOI : 10,1006 / jagm.1994.1028 , МР 1279270 .
  31. ^ a b c d Нешетржил, Ярослав ; Ossona де Мендес, Патрис (2012), разреженность: Графы, структура и алгоритмы , алгоритмы и комбинаторика, 28 ., Springer, С. 321-328, DOI : 10.1007 / 978-3-642-27875-4 , ISBN 978-3-642-27874-7, MR  2920058.
  32. ^ Бланкеншип, Р. (2003), Книжные вложения графов , доктор философии. докторская диссертация, факультет математики, Государственный университет Луизианы. Цитируется Nešetřil & Ossona de Mendez (2012) .
  33. ^ Бекос, Майкл А .; Брукдорфер, Тилль; Кауфманн, Майкл; Raftopoulou, Chrysanthi (2015), "1-планарные графы имеют постоянную толщину книги", Алгоритмы - ESA 2015 , Lecture Notes в области компьютерных наук, 9294 , Springer, С. 130-141,. DOI : 10.1007 / 978-3-662-48350 -3_12.
  34. ^ a b Бекос, Майкл; Кауфманн, Майкл; Зильке, Кристиан (2015), "Проблема вложения книг с точки зрения решения SAT", Proc. 23-й Международный симпозиум по рисованию графиков и визуализации сетей (GD 2015) , стр. 113–125..
  35. ^ Барат, Янош; Матушек, Иржи ; Вуд, Дэвид Р. (2006), «Графы с ограниченными степенями имеют произвольно большую геометрическую толщину», Электронный журнал комбинаторики , 13 (1): R3, doi : 10.37236 / 1029 , MR 2200531 .
  36. ^ а б Дуймович, Вида; Сидиропулос, Анастасиос; Вуд, Дэвид Р. (2015), 3-Monotone Expanders , arXiv : 1501.05020 , Bibcode : 2015arXiv150105020D, улучшая более ранний результат, показывающий существование расширителей с постоянным номером страницы из Bourgain, Jean (2009), «Expanders and Dimension extension », Comptes Rendus Mathématique , 347 (7–8): 357–362, doi : 10.1016 / j.crma .2009.02.009 , MR 2537230 ; Бургейн, Жан ; Yehudayoff, Амир (2013), "Разложение по SL 2 (ℝ) и монотонные экспандеры", геометрические и функционального анализа , 23 (1): 1-41, DOI : 10.1007 / s00039-012-0200-9 , МР 3037896 , S2CID 121554827  . См. Также Галил, Цви ; Каннан, Рави ; Семереди, Эндре (1989), "О 3-Pushdown графов с большими сепараторами", Combinatorica , 9 (1): 9-19, DOI : 10.1007 / BF02122679 , МР 1010295 , S2CID 37506294  ; Двир, Зеев; Wigderson, Avi (2010), "Монотонные расширители: конструкции и применения", Теория вычислений , 6 : 291-308, DOI : 10,4086 / toc.2010.v006a012 , МР 2770077 .
  37. ^ Хит, Ленвуд S .; Розенберг, Арнольд Л. (1992), "Разметка графики с использованием очередей", SIAM журнал по вычислениям , 21 (5): 927-958, DOI : 10,1137 / 0221055 , МР 1181408 .
  38. ^ Дуймович, Вида; Вуд, Дэвид Р. (2004), «О линейных схемах графов», Дискретная математика и теоретическая информатика , 6 (2): 339–357, MR 2081479 .
  39. ^ a b c Чанг, Фань РК ; Лейтон, Фрэнк Томпсон ; Розенберг, Арнольд Л. (1987), "Вложение графов в книгах: проблема компоновки с приложениями к СБИС" (PDF) , SIAM журнал на алгебраические и методы дискретной , 8 (1): 33-58, DOI : 10,1137 / 0608002 .
  40. ↑ Унгер, Вальтер (1992), «Сложность раскраски круговых графов», STACS 92: 9-й ежегодный симпозиум по теоретическим аспектам информатики, Кашан, Франция, 13–15 февраля 1992 г., Труды , конспекты лекций по информатике, 577 , Берлин: Springer, стр. 389–400, DOI : 10.1007 / 3-540-55210-3_199.
  41. ^ Унгер, Уолтер (1988), «О k-раскраске круговых графов», Труды 5-го симпозиума по теоретическим аспектам информатики (STACS '88) , конспекты лекций по информатике, 294 , Springer-Verlag, стр. 61–72, DOI : 10.1007 / BFb0035832.
  42. ^ a b c d Масуда, Сумио; Накадзима, Кадзуо; Кашивабара, Тошинобу; Фудзисава, Тосио (1990), "минимизация переходов в линейных вложений графов", IEEE Transactions по компьютерам , 39 (1): 124-127, DOI : 10,1109 / 12,46286 , MR 1032144 .
  43. ^ Garey, MR ; Джонсон, DS ; Миллер, Г.Л . ; Papadimitriou, СН (1980), "Сложность окраски круглые дуги и аккорды", SIAM журнал на алгебраических и дискретных методов , 1 (2): 216-227, DOI : 10,1137 / 0601025 , МР 0578325 .
  44. ^ a b c Хонг, Сок-Хи; Нагамочи, Хироши (2009), Вложение двухстраничной книги и планарность кластерного графа (PDF) , Технический отчет (изд. 2009-004), Департамент прикладной математики и физики, Университет Киото, Япония .
  45. ^ Анджелини, Патрицио; Ди Бартоломео, Марко; Ди Баттиста, Джузеппе (2013), «Реализация алгоритма тестирования встраивания двухстраничной книги», Отрисовка графика: 20-й Международный симпозиум, GD 2012, Редмонд, Вашингтон, США, 19–21 сентября 2012 г., Пересмотренные избранные статьи , конспекты лекций в области компьютерных наук, 7704 , Springer, С. 79-89,. Arxiv : 1209.0598 , DOI : 10.1007 / 978-3-642-36763-2_8 , MR 3067219 , S2CID 15360191  .
  46. ^ Nešetřil & Ossona де Мендес (2012) , следствие 18,1 р. 401.
  47. ^ Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2008), «Град и классы с ограниченным расширением. II. Алгоритмические аспекты», Европейский журнал комбинаторики , 29 (3): 777–791, arXiv : math / 0508324 , doi : 10.1016 / j.ejc .2006.07.014 , Руководство по эксплуатации 2397336 , S2CID 1139740  .
  48. ^ Nešetřil & Ossona де Мендес (2012) , теорема 18.7, стр. 405.
  49. ↑ Розенберг, Арнольд Л. (1986), «Вложения книг и интеграция в масштабе пластин», Труды семнадцатой Юго-Восточной международной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1986) , Congressus Numerantium, 54 , стр. 217–224, MR 0885282 .
  50. Перейти ↑ Knuth, Donald E. (1968), The Art Of Computer Programming Vol. 1 , Бостон: Addison-Wesley, раздел 2.2.1, упражнения 4 и 5, ISBN 0-201-89683-4, Руководство по ремонту  0286317 , OCLC  155842391.
  51. ^ Кайнен, Пол С. (1990), "Толщина книги графа. II", Труды Двадцатой Юго-Восточной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1989) , Congressus Numerantium, 71 , стр. 127–132, MR 1041623 .
  52. ^ Б Ваттенберг, М. (2002), "Arc диаграммы: визуализации структуры строк в", Труды IEEE симпозиума по визуализации информации (INFOVIS 2002) , стр. 110-116, DOI : 10,1109 / INFVIS.2002.1173155 , S2CID +881989 .
  53. ^ a b c Баур, Майкл; Брандес, Ульрик (2005), «Сокращение пересечений в круговых макетах», Ван Левен, Ян (редактор), Теоретико-графические концепции в компьютерных науках: 30-й международный семинар, WG 2004, Бад-Хоннеф, Германия, 21-23 июня, 2004, пересмотренная документы , Lecture Notes в области компьютерных наук, 3353 , Springer, С. 332-343,. DOI : 10.1007 / 978-3-540-30559-0_28.
  54. ^ a b Анджелини, Патрицио; Ди Баттиста, Джузеппе; Фрати, Фабрицио; Патриньяни, Маурицио; Руттер, Игнац (2012), «Проверка одновременной встраиваемости двух графов, пересечение которых является двусвязным или связным графом», Журнал дискретных алгоритмов , 14 : 150–172, DOI : 10.1016 / j.jda.2011.12.015 , MR 2922068 .
  55. ^ Б Вуд, Дэвид Р. (2002), «Кольцевая степень книга вложение и трехмерный ортогональный граф рисунок», график График: 9 - й Международного симпозиум, GD 2001, Вена, Австрия, 23-26 сентября, 2001, пересмотренная документы , Lecture Notes в области компьютерных наук, 2265 ., Springer, Berlin, С. 312-327, DOI : 10.1007 / 3-540-45848-4_25 , MR +1962433 .
  56. ^ Саати, Томас Л. (1964), «Минимальное количество пересечений в полных графах», Труды Национальной академии наук Соединенных Штатов Америки , 52 (3): 688–690, Bibcode : 1964PNAS ... 52..688S , DOI : 10.1073 / pnas.52.3.688 , МР 0166772 , КУП 300329 , PMID 16591215   .
  57. ^ Николсон, ТАД (1968), «процедура Перестановки для минимизации числа пересечений в сети», Труды Института инженеров - электриков , 115 : 21-26, DOI : 10,1049 / piee.1968.0004 , МР 0311416 .
  58. ^ Мияучи, Мики (2006), «Топологическая книга встраивания двудольных графов», « Транзакции IEICE по основам электроники, связи и компьютерных наук» , E89-A (5): 1223–1226, Bibcode : 2006IEITF..89.1223M , doi : 10.1093 / ietfec / e89-a.5.1223.
  59. ^ Джордано, Франческо; Лиотта, Джузеппе; Мчедлидзе, Тамара; Симвонис, Антониос (2007), "Вычисление восходящих топологических вложений книги восходящих плоских орграфов", Алгоритмы и вычисления: 18-й Международный симпозиум, ISAAC 2007, Сендай, Япония, 17–19 декабря 2007 г., Труды , Лекционные заметки по информатике, 4835 , Springer, С. 172-183,. дои : 10.1007 / 978-3-540-77120-3_17.
  60. ^ Он, Хунмэй; Сыкора, Ондрей (2004 г.), «Новые алгоритмы кругового рисования», Труды семинара по информационным технологиям - приложениям и теории (ITAT), Словакия, 15–19 сентября 2004 г..
  61. ^ Шахрохи, Фархад; Сикора, Ондрей; Секели, Ласло А .; Врт'о, Имрих (1995), "Вложения книг и числа скрещивания", Теоретико-графические концепции в компьютерных науках: 20-й международный семинар, WG '94, Херршинг, Германия, 16–18 июня 1994 г., Труды , Лекционные заметки на компьютере Science, 903 , Springer, стр. 256–268, DOI : 10.1007 / 3-540-59071-4_53.
  62. ^ Баннистер, Майкл Дж .; Эпштейн, Дэвид ; Саймонс, Джозеф А. (2013), "Сговорчивость с фиксированными параметрами минимизации пересечения почти-деревьев", Отрисовка графика: 21-й Международный симпозиум, GD 2013, Бордо, Франция, 23–25 сентября 2013 г., Пересмотренные избранные статьи , Лекционные заметки в Computer Science, 8242 , стр 340-351,. Arxiv : 1308,5741 , DOI : 10.1007 / 978-3-319-03841-4_30 , S2CID 10142319 .
  63. ^ Баннистер, Майкл Дж .; Эппштейн, Дэвид (2014), «Минимизация пересечений для одностраничных и двухстраничных чертежей графиков с ограниченной шириной дерева», Proc. 22-е межд. Symp. Graph Drawing (GD 2014) , Lecture Notes in Computer Science, 8871 , Springer-Verlag, pp. 210–221, arXiv : 1408.6321 , doi : 10.1007 / 978-3-662-45803-7_18 , MR 3333228 .
  64. ^ Блин, Гийом; Фертин, Гийом; Русу, Ирена; Синокет, Кристин (2007), «Повышение жесткости сравнения вторичных структур РНК», Комбинаторика, алгоритмы, вероятностные и экспериментальные методологии: Первый международный симпозиум, ESCAPE 2007, Ханчжоу, Китай, 7-9 апреля 2007 г., Пересмотренные избранные статьи (PDF ) , Конспект лекций по информатике, 4614 , стр. 140–151, DOI : 10.1007 / 978-3-540-74450-4_13 .
  65. ^ Клот, Питер; Добрев, Стефан; Доту, Иван; Кранакис, Эвангелос; Крижанц, Дэнни; Уррутиа, Хорхе (2012), "На странице числа вторичных структур РНК с псевдоузлов", Журнал математической биологии , 65 (6-7): 1337-1357, DOI : 10.1007 / s00285-011-0493-6 , PMID 22159642 , S2CID 8700502  .
  66. ^ Паван, А .; Тевари, Рагхунатх; Vinodchandran, Н. В. (2012), "О мощности однозначности в лог-пространстве", вычислительная сложность , 21 (4): 643-670, Arxiv : 1001,2034 , DOI : 10.1007 / s00037-012-0047-3 , МР 2988774 , S2CID 8666071  .
  67. ^ Галил, Цви ; Каннан, Рави ; Семереди, Эндре (1989), «О нетривиальных сепараторов для к-страниц графиков и моделирования недетерминированными один Тьюринга машин», журнал компьютерных и системных наук , 38 (1): 134-149, DOI : 10.1016 / 0022-0000 (89) 90036-6.
  68. ^ Маккензи, Томас; Овербей, Шеннон (2010), «Книжные вложения и делители нуля», Ars Combinatoria , 95 : 55–63, MR 2656248 .
  69. ^ Дынников, IA (1999), "Три страницы подход к теории узлов кодирования и локальные движения.", Российская Академия наук , 33 (4): 25-37, 96, DOI : 10.1007 / BF02467109 , MR 1746427 , S2CID 121089736  .
  70. ^ Дынников, И. А. (2001), "Новый способ представления ссылок, одномерный формализм и распутывания технологии", Acta Applicandae Mathematicae , 69 (3): 243-283, DOI : 10,1023 / A: 1014299416618 , MR 1885279 , S2CID 116488382  .