Вложение книги - Book embedding

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

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

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

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

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

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

История

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

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

Определения

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

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

А книжный рисунок конечного графа грамм на книгу B это Рисование из грамм на B такая, что каждая вершина грамм нарисован как точка на позвоночнике B, и каждый край грамм нарисован как изгиб что находится на одной странице B. В k-страница номер буккроссинга из грамм это минимум количество переходов в kстраничный книжный рисунок.[11]

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

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

Конкретные графики

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

Номер пересечения на двух страницах полного графика Kп является

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

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

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

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

[10][20]

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

Характеристики

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

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

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

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

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

Поведение по подразделениям

Вопрос, Web Fundamentals.svgНерешенная проблема в математике:
Может ли толщина книги графа быть ограничена сверху функцией толщины книги его подразделения?
(больше нерешенных задач по математике)
Толщина книги ромбовидной диаграммы увеличивается после разделения кромок.

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

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

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

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

Каждый мелкий минор графа ограниченной книжной толщины является разреженный граф, у которого отношение ребер к вершинам ограничено константой, зависящей только от глубины минора и толщины книги. То есть в терминологии Нешетржил и Оссона де Мендес (2012), графики ограниченной толщины книги имеют ограниченное расширение.[31] Однако даже графики ограниченного степень, гораздо более жесткое требование, чем ограниченное расширение, может иметь неограниченную толщину книги.[35]

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

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

Вычислительная сложность

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

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

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

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

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

Бекос, Кауфманн и Цильке (2015) описать систему для поиска оптимальных вложений книг, преобразовав задачу в пример Проблема логической выполнимости и применение решателя SAT к получившейся проблеме. Они заявляют, что их система способна найти оптимальное вложение для 400-вершинных максимальные планарные графы примерно за 20 минут, и что он был успешно применен к графу с 600 вершинами, который Яннакакис предложил как требующий четырех страниц, но, как оказалось, для этого потребовалось всего три страницы.[34]

Приложения

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

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

Сортировка стопки

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

Контроль дорожного движения

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

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

Рисование графика

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

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

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

Круговая планировка Хваталь граф

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

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

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

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

Сворачивание РНК

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

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

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

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

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

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

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

Другие области математики

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

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

Рекомендации

  1. ^ а б Персингер, К. А. (1966), "Подмножества п-книги в E3", Тихоокеанский математический журнал, 18: 169–173, Дои:10.2140 / pjm.1966.18.169, МИСТЕР  0195077.
  2. ^ а б Атнеозен, Гейл Адель (1968), О вложимости компактов в п-Книги: внутренние и внешние свойства, Кандидат наук. Тезис, Университет штата Мичиган, п. 79, МИСТЕР  2617705. Смотрите также Атнеозен, Гейл Х. (1972), "Одномерный п-листный континуум " (PDF), Fundamenta Mathematicae, 74 (1): 43–45, Дои:10.4064 / fm-74-1-43-45, МИСТЕР  0293592.
  3. ^ Кайнен, Пол К. (1974), «Некоторые недавние результаты в топологической теории графов», в Bari, Ruth A .; Харари, Фрэнк (ред.), Графы и комбинаторика (Труды столичной конференции по теории графов и комбинаторике в Университете Джорджа Вашингтона 18–22 июня 1973 г.), Конспект лекций по математике, 406, стр. 76–108.
  4. ^ Оллманн, Л. Тейлор (1973), «О книжных толщинах различных графов», у Хоффмана, Фредерика; Левоу, Рой Б.; Томас, Роберт С. Д. (ред.), Proc. 4-я Юго-Восточная конференция по комбинаторике, теории графов и вычислениям, Congressus Numerantium, VIII, п. 459.
  5. ^ а б c Яннакакис, Михалис (1989), «Вложение плоских графов в четыре страницы», Журнал компьютерных и системных наук, 38: 36–67, Дои:10.1016/0022-0000(89)90032-9
  6. ^ а б c Яннакакис, Михалис (1986), «Четыре страницы необходимы и достаточно для плоских графов», Материалы 18-го симпозиума ACM по теории вычислений (STOC '86), стр. 104–108, Дои:10.1145/12130.12141, ISBN  0-89791-193-8, S2CID  5359519.
  7. ^ а б c d е Хаслингер, Кристиан; Стадлер, Питер Ф. (1999), "Структуры РНК с псевдузлами: теоретико-графические, комбинаторные и статистические свойства", Вестник математической биологии, 61 (3): 437–467, Дои:10.1006 / Bulm.1998.0085, ЧВК  7197269, PMID  17883226.
  8. ^ Хейлз, Т. (1997), «Сферические упаковки. II», Дискретная и вычислительная геометрия, 18 (2): 135–149, Дои:10.1007 / PL00009312, МИСТЕР  1455511.
  9. ^ Терминология «позвоночник» и «страницы» является более стандартной в современных теоретико-графических подходах к предмету. О терминологии «спина» и «листья» см. Персингер (1966).
  10. ^ а б c d е ж грамм Bernhart, Frank R .; Кайнен, Пол К. (1979), «Книжная толщина графа», Журнал комбинаторной теории, Серия B, 27 (3): 320–331, Дои:10.1016/0095-8956(79)90021-2, МИСТЕР  0554297.
  11. ^ Шахрохи, Фархад; Секели, Ласло А .; Сикора, Ондрей; Vrťo, Имрих (1996), "Буккроссинг числа графа", Журнал теории графов, 21 (4): 413–424, Дои:10.1002 / (SICI) 1097-0118 (199604) 21: 4 <413 :: AID-JGT7> 3.3.CO; 2-5, МИСТЕР  1377615.
  12. ^ а б c Хит, Ленвуд С. (1987), "Вложение внешнепланарных графов в небольшие книги", Журнал SIAM по алгебраическим и дискретным методам, 8 (2): 198–218, Дои:10.1137/0608018, МИСТЕР  0881181.
  13. ^ Stöhr, Елена (1988), "Компромисс между номером страницы и шириной страницы книжных вложений графиков", Информация и вычисления, 79 (2): 155–162, Дои:10.1016/0890-5401(88)90036-3, МИСТЕР  0968104.
  14. ^ Stöhr, Елена (1991), "Ширина страницы трехвалентных планарных графов", Дискретная математика, 89 (1): 43–49, Дои:10.1016 / 0012-365X (91) 90398-L, МИСТЕР  1108073.
  15. ^ а б c Эномото, Хико; Мияути, Мики Симабара (1999), «Вложение графиков в трехстраничную книгу с О(M бревно N) пересечения краев по корешку ", Журнал SIAM по дискретной математике, 12 (3): 337–341, Дои:10.1137 / S0895480195280319, МИСТЕР  1710241.
  16. ^ а б c Бланкеншип, Робин; Опоровский, Богдан (1999), Рисование частей полного и полного двудольного графа на книгах, Технический отчет 1999-4, математический факультет Университета штата Луизиана, CiteSeerX  10.1.1.36.4358.
  17. ^ Эномото, Хико; Мияути, Мики Шимабара; Ота, Кацухиро (1999), "Нижние оценки количества переходов ребер через позвоночник в топологическом книжном вложении графа", Дискретная прикладная математика, 92 (2–3): 149–155, Дои:10.1016 / S0166-218X (99) 00044-X, МИСТЕР  1697548.
  18. ^ Абрего, Бернардо М .; Айхольцер, Освин; Фернандес-Мерчант, Сильвия; Рамос, Педро; Салазар, Геласио (2012), "2-страничный перекрестный номер Kп (расширенная аннотация) ", Материалы 28-го ежегодного симпозиума по вычислительной геометрии (SCG'12), ACM, Нью-Йорк, стр. 397–403, Дои:10.1145/2261250.2261310, МИСТЕР  3050657, S2CID  8344088.
  19. ^ Дополнительные результаты о книжной толщине полных двудольных графов см. Эномото, Хико; Накамигава, Томоки; Ота, Кацухиро (1997), "О номере страницы полных двудольных графов", Журнал комбинаторной теории, Серия B, 71 (1): 111–120, Дои:10.1006 / jctb.1997.1773, МИСТЕР  1469870; де Клерк, Этьен; Пасечник, Дмитрий В .; Салазар, Геласио (2014), «Книжные рисунки полных двудольных графов», Дискретная прикладная математика, 167: 80–93, arXiv:1210.2918, Дои:10.1016 / j.dam.2013.11.001, МИСТЕР  3166108, S2CID  40920263.
  20. ^ Сперфельд, Конрад (2013), "На номере страницы полных нечетно-долевых графов", Дискретная математика, 313 (17): 1689–1696, Дои:10.1016 / j.disc.2013.04.028, МИСТЕР  3061004.
  21. ^ Хасунума, Тору; Шибата, Юкио (1997), «Встраивание де Брейна, Каутца и сетей обмена в случайном порядке в книгах», Дискретная прикладная математика, 78 (1–3): 103–116, Дои:10.1016 / S0166-218X (97) 00009-7, МИСТЕР  1475820; Танака, Юки; Сибата, Юкио (2010), "О номере страницы кубически связанных циклов", Математика в информатике, 3 (1): 109–117, Дои:10.1007 / s11786-009-0012-у, МИСТЕР  2596254, S2CID  11830437. Смотрите также Обренич, Бояна (1993), "Вложение де Брейна и тасование-обмен графов на пяти страницах", Журнал SIAM по дискретной математике, 6 (4): 642–654, Дои:10.1137/0406049, МИСТЕР  1241401.
  22. ^ Бекос, Майкл А .; Гронеманн, Мартин; Рафтопулу, Хрисанти Н. (2014), "Двухстраничные книжные вложения 4-плоских графов", Материалы 31-го симпозиума по теоретическим аспектам информатики, стр. 137–148, arXiv:1401.0684, Дои:10.4230 / LIPIcs.STACS.2014.137.
  23. ^ Хит, Ленни (1984), "Вложение плоских графов на семи страницах", Материалы 25-го ежегодного симпозиума по основам информатики, стр. 74–83, Дои:10.1109 / SFCS.1984.715903.
  24. ^ а б Бекос, Майкл А .; Кауфманн, Майкл; Клют, Фабиан; Пупырев, Сергей; Рафтопулу, Хризанти; Иккердт, Торстен (2020), Четыре страницы действительно необходимы для плоских графов, arXiv:2004.07630.
  25. ^ а б c Эппштейн, Дэвид (2001), Разделение геометрической толщины и толщины книги, arXiv:math.CO/0109195.
  26. ^ Вуд, Дэвид (19 января 2009 г.), «Книжная толщина разделов», Открытый Проблемный Сад, получено 2013-02-05.
  27. ^ а б Дуймович, Вида; Вуд, Дэвид Р. (2007), «Параметры ширины дерева и геометрической толщины графика», Дискретная и вычислительная геометрия, 37 (4): 641–670, arXiv:математика / 0503553, Дои:10.1007 / s00454-007-1318-7, S2CID  9141367.
  28. ^ Ganley, Joseph L .; Хит, Ленвуд С. (2001), "Номер страницы k-деревья О(k)", Дискретная прикладная математика, 109 (3): 215–221, Дои:10.1016 / S0166-218X (00) 00178-5, МИСТЕР  1818238.
  29. ^ Малиц, Сет М. (1994), "Графики с E края имеют номер страницы О(√E)", Журнал алгоритмов, 17 (1): 71–84, Дои:10.1006 / jagm.1994.1027, МИСТЕР  1279269.
  30. ^ Малиц, Сет М. (1994), "Род грамм графики имеют номер страницы О(√грамм)", Журнал алгоритмов, 17 (1): 85–109, Дои:10.1006 / jagm.1994.1028, МИСТЕР  1279270.
  31. ^ а б c d Нешетржил, Ярослав; Оссона де Мендес, Патрис (2012), Разреженность: графики, структуры и алгоритмы, Алгоритмы и комбинаторика, 28, Springer, стр. 321–328, Дои:10.1007/978-3-642-27875-4, ISBN  978-3-642-27874-7, МИСТЕР  2920058.
  32. ^ Бланкеншип, Р. (2003), Книжные вложения графов, Кандидат наук. докторская диссертация, факультет математики, Государственный университет Луизианы. Как цитирует Нешетржил и Оссона де Мендес (2012).
  33. ^ Бекос, Майкл А .; Брукдорфер, Тилль; Кауфманн, Майкл; Рафтопулу, Хрисанти (2015), «1-планарные графы имеют постоянную толщину книги», Алгоритмы - ESA 2015, Конспект лекций по информатике, 9294, Springer, стр. 130–141, Дои:10.1007/978-3-662-48350-3_12.
  34. ^ а б Бекос, Михаил; Кауфманн, Майкл; Зильке, Кристиан (2015), «Проблема вложения книг с точки зрения SAT-решения», Proc. 23-й Международный симпозиум по рисованию графиков и визуализации сетей (GD 2015), стр. 113–125.
  35. ^ Барат, Янош; Матушек, Иржи; Вуд, Дэвид Р. (2006), «Графы ограниченной степени имеют сколь угодно большую геометрическую толщину», Электронный журнал комбинаторики, 13 (1): R3, Дои:10.37236/1029, МИСТЕР  2200531.
  36. ^ а б Дуймович, Вида; Сидиропулос, Анастасиос; Вуд, Дэвид Р. (2015), 3-монотонные расширители, arXiv:1501.05020, Bibcode:2015arXiv150105020D, улучшая предыдущий результат, показывающий существование расширителей с постоянным номером страницы из Бургейн, Жан (2009), «Расширители и расширение размеров», Comptes Rendus Mathématique, 347 (7–8): 357–362, Дои:10.1016 / j.crma.2009.02.009, МИСТЕР  2537230; Бургейн, Жан; Иегудаофф, Амир (2013), «Расширение в SL2(ℝ) и монотонные расширители », Геометрический и функциональный анализ, 23 (1): 1–41, Дои:10.1007 / s00039-012-0200-9, МИСТЕР  3037896, S2CID  121554827. Смотрите также Галил, Цви; Каннан, Рави; Семереди, Эндре (1989), "О трехпозиционных графиках с большими разделителями", Комбинаторика, 9 (1): 9–19, Дои:10.1007 / BF02122679, МИСТЕР  1010295, S2CID  37506294; Двир, Зеев; Вигдерсон, Ави (2010), «Монотонные расширители: конструкции и приложения», Теория вычислений, 6: 291–308, Дои:10.4086 / toc.2010.v006a012, МИСТЕР  2770077.
  37. ^ Heath, Lenwood S .; Розенберг, Арнольд Л. (1992), "Разметка графов с использованием очередей", SIAM Журнал по вычислениям, 21 (5): 927–958, Дои:10.1137/0221055, МИСТЕР  1181408.
  38. ^ Дуймович, Вида; Вуд, Дэвид Р. (2004), «О линейных схемах графов», Дискретная математика и теоретическая информатика, 6 (2): 339–357, МИСТЕР  2081479.
  39. ^ а б c Чунг, Фан Р. К.; Лейтон, Фрэнк Томпсон; Розенберг, Арнольд Л. (1987), «Встраивание графиков в книги: проблема компоновки приложений для проектирования СБИС» (PDF), Журнал SIAM по алгебраическим и дискретным методам, 8 (1): 33–58, Дои:10.1137/0608002.
  40. ^ Унгер, Вальтер (1992), "Сложность раскраски круговых графов", STACS 92: 9-й ежегодный симпозиум по теоретическим аспектам информатики, Кашан, Франция, 13–15 февраля 1992 г., Труды, Конспект лекций по информатике, 577, Берлин: Springer, стр. 389–400, Дои:10.1007/3-540-55210-3_199.
  41. ^ Унгер, Вальтер (1988), "О k-раскраске круговых графов", Материалы 5-го симпозиума по теоретическим аспектам информатики (STACS '88), Конспект лекций по информатике, 294, Springer-Verlag, стр. 61–72, Дои:10.1007 / BFb0035832.
  42. ^ а б c d Масуда, Сумио; Накадзима, Кадзуо; Кашивабара, Тошинобу; Fujisawa, Toshio (1990), "Минимизация пересечений в линейных вложениях графов", Транзакции IEEE на компьютерах, 39 (1): 124–127, Дои:10.1109/12.46286, МИСТЕР  1032144.
  43. ^ Гарей, М.; Джонсон, Д.С.; Миллер, Г.Л.; Пападимитриу, К. (1980), «Сложность раскраски дуг и хорд окружностей», Журнал SIAM по алгебраическим и дискретным методам, 1 (2): 216–227, Дои:10.1137/0601025, МИСТЕР  0578325.
  44. ^ а б c Хонг, Сок-Хи; Нагамочи, Хироши (2009), Встраивание двухстраничной книги и планарность кластерного графа (PDF), Технический отчет (изд. 2009-004), кафедра прикладной математики и физики, Университет Киото, Япония.
  45. ^ Анджелини, Патрицио; Ди Бартоломео, Марко; Ди Баттиста, Джузеппе (2013), «Реализация алгоритма тестирования встраивания двухстраничной книги», Графический рисунок: 20-й Международный симпозиум, GD 2012, Редмонд, Вашингтон, США, 19–21 сентября 2012 г., Пересмотренные избранные статьи, Конспект лекций по информатике, 7704, Springer, стр. 79–89, arXiv:1209.0598, Дои:10.1007/978-3-642-36763-2_8, МИСТЕР  3067219, S2CID  15360191.
  46. ^ Нешетржил и Оссона де Мендес (2012), Следствие 18.1, с. 401.
  47. ^ Нешетржил, Ярослав; Оссона де Мендес, Патрис (2008), «Град и классы с ограниченным расширением. II. Алгоритмические аспекты», Европейский журнал комбинаторики, 29 (3): 777–791, arXiv:математика / 0508324, Дои:10.1016 / j.ejc.2006.07.014, МИСТЕР  2397336, S2CID  1139740.
  48. ^ Нешетржил и Оссона де Мендес (2012), Теорема 18.7, с. 405.
  49. ^ Розенберг, Арнольд Л. (1986), «Книжные вложения и интеграция в масштабе пластин», Труды семнадцатой Юго-Восточной международной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1986), Congressus Numerantium, 54, стр. 217–224, МИСТЕР  0885282.
  50. ^ Кнут, Дональд Э. (1968), Искусство программирования Том. 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, МИСТЕР  1041623.
  52. ^ а б Ваттенберг, М. (2002), «Дуговые диаграммы: визуализация структуры в строках», Материалы симпозиума IEEE по визуализации информации (INFOVIS 2002), стр. 110–116, Дои:10.1109 / INFVIS.2002.1173155, S2CID  881989.
  53. ^ а б c Баур, Майкл; Брандес, Ульрик (2005), «Уменьшение пересечения в круговых схемах», Ван Левен, Ян (ред.), Теоретико-графические концепции в компьютерных науках: 30-й международный семинар, WG 2004, Бад-Хоннеф, Германия, 21-23 июня 2004 г., исправленные статьи, Конспект лекций по информатике, 3353, Springer, стр. 332–343, Дои:10.1007/978-3-540-30559-0_28.
  54. ^ а б Анджелини, Патрицио; Ди Баттиста, Джузеппе; Фрати, Фабрицио; Патриньяни, Маурицио; Руттер, Игнац (2012), «Тестирование одновременной вложимости двух графов, пересечение которых является двусвязным или связным графом», Журнал дискретных алгоритмов, 14: 150–172, Дои:10.1016 / j.jda.2011.12.015, МИСТЕР  2922068.
  55. ^ а б Вуд, Дэвид Р. (2002), "Вложения книги ограниченной степени и рисование трехмерного ортогонального графа", Графический рисунок: 9-й Международный симпозиум, GD 2001, Вена, Австрия, 23–26 сентября 2001 г., исправленные статьи, Конспект лекций по информатике, 2265, Springer, Берлин, стр. 312–327, Дои:10.1007/3-540-45848-4_25, МИСТЕР  1962433.
  56. ^ Саати, Томас Л. (1964), «Минимальное количество пересечений в полных графах», Труды Национальной академии наук Соединенных Штатов Америки, 52 (3): 688–690, Bibcode:1964ПНАС ... 52..688С, Дои:10.1073 / pnas.52.3.688, МИСТЕР  0166772, ЧВК  300329, PMID  16591215.
  57. ^ Николсон, Т. А. Дж. (1968), "Процедура перестановки для минимизации количества пересечений в сети", Труды института инженеров-электриков, 115: 21–26, Дои:10.1049 / piee.1968.0004, МИСТЕР  0311416.
  58. ^ Мияучи, Мики (2006), "Топологическое книжное вложение двудольных графов", Сделки IEICE по основам электроники, связи и компьютерных наук, E89-A (5): 1223–1226, Bibcode:2006IEITF..89.1223M, Дои: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. ^ Шахрохи, Фархад; Сикора, Ондрей; Секели, Ласло А .; Vrt'o, Имрих (1995), "Книжные вложения и числа пересечения", Теоретико-графические концепции в компьютерных науках: 20-й международный семинар, WG '94, Херршинг, Германия, 16–18 июня 1994 г., Труды, Конспект лекций по информатике, 903, Springer, стр. 256–268, Дои:10.1007/3-540-59071-4_53.
  62. ^ Баннистер, Майкл Дж .; Эппштейн, Дэвид; Саймонс, Джозеф А. (2013), "Управляемость с фиксированным параметром минимизации пересечения почти-деревьев", Графический рисунок: 21-й Международный симпозиум, GD 2013, Бордо, Франция, 23–25 сентября 2013 г., отредактированные избранные статьи, Конспект лекций по информатике, 8242, стр. 340–351, arXiv:1308.5741, Дои:10.1007/978-3-319-03841-4_30, S2CID  10142319.
  63. ^ Баннистер, Майкл Дж .; Эппштейн, Дэвид (2014), «Минимизация пересечений для 1-страничных и 2-страничных чертежей графиков с ограниченной шириной дерева», Proc. 22-й Int. Symp. Графический рисунок (GD 2014), Конспект лекций по информатике, 8871, Springer-Verlag, стр. 210–221, arXiv:1408.6321, Дои:10.1007/978-3-662-45803-7_18, МИСТЕР  3333228.
  64. ^ Блин, Гийом; Фертин, Гийом; Русу, Ирена; Синокет, Кристин (2007), «Повышение жесткости сравнения вторичной структуры РНК», Комбинаторика, алгоритмы, вероятностные и экспериментальные методологии: первый международный симпозиум, ESCAPE 2007, Ханчжоу, Китай, 7-9 апреля 2007 г., исправленные избранные статьи (PDF), Конспект лекций по информатике, 4614, стр. 140–151, Дои:10.1007/978-3-540-74450-4_13.
  65. ^ Клот, Петр; Добрев, Стефан; Доту, Иван; Кранакис, Эвангелос; Крижанц, Дэнни; Уррутия, Хорхе (2012), «На странице номера вторичных структур РНК с псевдоузлами», Журнал математической биологии, 65 (6–7): 1337–1357, Дои:10.1007 / s00285-011-0493-6, PMID  22159642, S2CID  8700502.
  66. ^ Паван, А .; Тевари, Рагхунатх; Винодчандран, Н. В. (2012), "О силе однозначности в лог-пространстве", Вычислительная сложность, 21 (4): 643–670, arXiv:1001.2034, Дои:10.1007 / s00037-012-0047-3, МИСТЕР  2988774, S2CID  8666071.
  67. ^ Галил, Цви; Каннан, Рави; Семереди, Эндре (1989), "О нетривиальных разделителях для k-страничных графов и моделировании недетерминированными однополосными машинами Тьюринга" Журнал компьютерных и системных наук, 38 (1): 134–149, Дои:10.1016/0022-0000(89)90036-6.
  68. ^ Маккензи, Томас; Overbay, Шеннон (2010), "Книжные вложения и делители нуля", Ars Combinatoria, 95: 55–63, МИСТЕР  2656248.
  69. ^ Дынников, И. А. (1999), "Трехстраничный подход к теории узлов. Кодирование и локальные движения", Российская Академия Наук, 33 (4): 25–37, 96, Дои:10.1007 / BF02467109, МИСТЕР  1746427, S2CID  121089736.
  70. ^ Дынников, И. А. (2001), «Новый способ представления связей, одномерный формализм и технология распутывания», Acta Applicandae Mathematicae, 69 (3): 243–283, Дои:10.1023 / А: 1014299416618, МИСТЕР  1885279, S2CID  116488382.