Встраивание книги

Расположение графика на нескольких полуплоскостях

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

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

Каждый граф с n вершинами имеет не более толщины книги , и эта формула дает точную толщину книги для полных графов . Графы с толщиной книги один являются внешнепланарными графами . Графы с книжной толщиной не более двух являются субгамильтоновыми графами , которые всегда плоские ; в более общем смысле каждый планарный граф имеет толщину книги не более четырех. Все семейства минорно-замкнутых графов , и в частности графы с ограниченной шириной дерева или ограниченным родом , также имеют ограниченную толщину книги. Определить точную толщину книги данного графа NP-трудно , зная или не зная фиксированного порядка вершин вдоль корешка книги. Проверка существования вложения графа в трехстраничную книгу при фиксированном порядке вершин вдоль позвоночника вложения имеет неизвестную вычислительную сложность: неизвестно, что он разрешим за полиномиальное время, и не известно, что он NP-труден. . ${\displaystyle \lceil n/2\rceil }$

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

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

История

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

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

Определения

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

Это одностраничное вложение ромбовидного графа имеет ширину страницы 3, поскольку желтый луч пересекает три ребра.

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

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

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

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

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

Как показано на первом рисунке, толщина книги полного графа K ₅ равна трем: в случае неплоского графа толщина книги больше двух, но существует вложение книги с тремя страницами. В более общем смысле, толщина книги каждого полного графа с n ≥ 4 вершинами равна ровно . Этот результат также дает верхнюю границу максимально возможной толщины книги любого n -вершинного графа. ^[10] ${\displaystyle \lceil n/2\rceil }$

Число пересечений двух страниц полного графа K _n равно

${\displaystyle {\frac {1}{4}}{\biggl \lfloor }{\frac {n}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {n-1}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {n-2}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {n-3}{2}}{\biggr \rfloor },}$

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

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

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

${\displaystyle \left\lceil {\frac {k(r-1)}{2}}\right\rceil \leq t\leq \left\lceil {\frac {kr}{2}}\right\rceil }$

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

${\displaystyle t\leq (r-1)\left\lceil {\frac {k}{2}}\right\rceil +\left\lceil {\frac {k}{4}}\right\rceil .}$^{[10] [20]}

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

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

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

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

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

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

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

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

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

Разделение каждого ребра графа на пути с двумя ребрами путем добавления новых вершин внутри каждого ребра иногда может увеличить толщину его книги. Например, ромбовидный граф имеет толщину книги один (он внешнепланарный), но его подразделение имеет толщину книги два (он плоский и субгамильтонов, но не внешнепланарный). Однако этот процесс подразделения также может иногда значительно уменьшить толщину книги разделенного графа. Например, толщина книги полного графа K _n пропорциональна числу его вершин, но разделение каждого из его ребер на путь с двумя ребрами дает подразделение, толщина книги которого намного меньше, всего . ^[25] Несмотря на существование подобных примеров, Бланкеншип и Опоровски (1999) предположили , что толщина книги подразделения не может быть слишком меньше, чем толщина исходного графа. В частности, они предположили, что существует функция f такая, что для каждого графа G и для графа H , образованного заменой каждого ребра в G путем с двумя ребрами, если толщина книги H равна t , то толщина книги G не более f ( t ) . ^[16] Их гипотеза оказалась ложной: графы, образованные декартовым произведением звезд и треугольных мозаик, имеют неограниченную толщину книги, но разделение их ребер на пути с шестью ребрами уменьшает толщину книги до трех. ^[26] ${\displaystyle O({\sqrt {n}})}$

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

Толщина книги связана с толщиной — количеством плоских графов, необходимых для покрытия ребер данного графа. Граф G имеет толщину θ, если его можно нарисовать на плоскости, а его ребра окрашены в цвета θ так, что ребра одного цвета друг с другом не пересекаются. Аналогично, граф 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] ${\displaystyle O({\sqrt {m}})}$ ${\displaystyle O({\sqrt {g}})}$

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

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

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

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

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

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

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

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

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

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

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

Для одностраничных рисунков любого стиля важно, чтобы количество пересечений было небольшим, чтобы уменьшить визуальный беспорядок рисунка. Минимизация количества пересечений является NP-полной ^[43] , но может быть аппроксимирована коэффициентом аппроксимации O (log ²  n ) , где n — количество вершин. ^[62] Минимизация числа пересечений на одной или двух страницах возможна с фиксированным параметром, если параметризована цикломатическим числом данного графа или комбинацией числа пересечений и ширины дерева графа. ^{[63] [64]} Также были разработаны эвристические методы снижения сложности пересечения, основанные, например, на тщательном порядке вставки вершин и на локальной оптимизации . ^[54]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Персингер, Калифорния (1966), «Подмножества n -книг в E ³ », Pacific Journal of Mathematics , 18 : 169–173, doi : 10.2140/pjm.1966.18.169 , MR  0195077.
2. Atneosen, Гейл Адель (1968), О вложимости компактов в n-книги: внутренние и внешние свойства, доктор философии. диссертация, Университет штата Мичиган , с. 79, МР  2617705. См. также Атнеосен, Гейл Х. (1972), «Одномерные n-листные континуумы» (PDF) , Fundamenta Mathematicae , 74 (1): 43–45, doi : 10.4064/fm-74-1-43-45 , МР  0293592.
3. Кайнен, Пол К. (1974), «Некоторые недавние результаты в топологической теории графов», в Бари, Рут А.; Харари, Фрэнк (ред.), Графы и комбинаторика (Материалы столичной конференции по теории графов и комбинаторике в Университете Джорджа Вашингтона, 18–22 июня 1973 г.) , Конспекты лекций по математике, том. 406, стр. 76–108..
4. Оллманн, Л. Тейлор (1973), «О толщине книг различных графиков», Хоффман, Фредерик; Левоу, Рой Б.; Томас, Роберт С.Д. (ред.), Proc. 4-я Юго-Восточная конференция по комбинаторике, теории графов и вычислениям , Congressus Numerantium, vol. VIII, с. 459.
5. Яннакакис, Михалис (1989), «Вложение плоских графов на четыре страницы», Журнал компьютерных и системных наук , 38 : 36–67, doi : 10.1016/0022-0000(89)90032-9
6. Яннакакис, Михалис (1986), «Четыре страницы необходимы и достаточны для плоских графов», Труды 18-го симпозиума ACM по теории вычислений (STOC '86) , стр. 104–108, doi : 10.1145/12130.12141, ISBN 0-89791-193-8, S2CID  5359519.
7. Хаслингер, Кристиан; Стадлер, Питер Ф. (1999), «Структуры РНК с псевдоузлами: теоретико-графовые, комбинаторные и статистические свойства», Бюллетень математической биологии , 61 (3): 437–467, doi : 10.1006/bulm.1998.0085, ПМК 7197269 , ПМИД  17883226 .
8. Хейлз, TC (1997), «Сферические упаковки. II», Дискретная и вычислительная геометрия , 18 (2): 135–149, doi : 10.1007/PL00009312 , hdl : 2027.42/42419 , MR  1455511.
9. Терминология «позвоночник» и «страницы» более стандартна в современных теоретико-графовых подходах к этому предмету. Терминологию «спинка» и «листья» см. в Persinger (1966).
10. Бернхарт, Фрэнк Р.; Кайнен, Пол К. (1979), «Толщина графа в книге», Журнал комбинаторной теории , серия B, 27 (3): 320–331, doi : 10.1016/0095-8956(79)90021-2 , MR  0554297.
11. Шахрохи, Фархад; Секели, Ласло А.; Сикора, Ондрей; Вртё, Имрих (1996), «Книжное число пересечений графа», Journal of Graph Theory , 21 (4): 413–424, doi : 10.1002/(SICI)1097-0118(199604)21:4<413: :AID-JGT7>3.3.CO;2-5, MR  1377615.
12. Хит, Ленвуд С. (1987), «Вложение внешнепланарных графов в небольшие книги», SIAM Journal on Algebraic and Discrete Methods , 8 (2): 198–218, doi : 10.1137/0608018, MR  0881181.
13. Штёр, Елена (1988), «Компромисс между количеством страниц и шириной страницы вложений графиков в книгу», Information and Computation , 79 (2): 155–162, doi : 10.1016/0890-5401(88)90036 -3 , МР  0968104.
14. Штер, Елена (1991), «Ширина страницы трехвалентных плоских графов», Discrete Mathematics , 89 (1): 43–49, doi : 10.1016/0012-365X(91)90398-L , MR  1108073.
15. Эномото, Хикоэ; Мияучи, Мики Симабара (1999), «Вложение графиков в трехстраничную книгу с O ( M log N ) пересечениями ребер через позвоночник», SIAM Journal on Discrete Mathematics , 12 (3): 337–341, doi : 10.1137/ С0895480195280319, МР  1710241.
16. Бланкеншип, Робин; Опоровски, Богдан (1999), Рисование подразделений полных и полных двудольных графов в книгах , Технический отчет 1999-4, факультет математики, Университет штата Луизиана, CiteSeerX 10.1.1.36.4358 .
17. Эномото, Хикоэ; Мияучи, Мики Симабара; Ота, Кацухиро (1999), «Нижние оценки количества пересечений ребер по позвоночнику в топологической книге, встраивающей граф», Discrete Applied Mathematics , 92 (2–3): 149–155, doi : 10.1016/S0166 -218X(99)00044-X , МР  1697548.
18. Абрего, Бернардо М.; Айххольцер, Освин; Фернандес-Терчант, Сильвия; Рамос, Педро; Салазар, Геласио (2012), «Двухстраничное число пересечений K _n (расширенный тезис)», Труды 28-го ежегодного симпозиума по вычислительной геометрии (SCG'12) , ACM, Нью-Йорк, стр. 397–403, doi :10.1145/2261250.2261310, MR  3050657, S2CID  8344088.
19. Дополнительные результаты о толщине книги полных двудольных графов см. в Enomoto, Hikoe; Накамигава, Томоки; Ота, Кацухиро (1997), «О номере страницы полных двудольных графов», Журнал комбинаторной теории , серия B, 71 (1): 111–120, doi : 10.1006/jctb.1997.1773 , MR  1469870; де Клерк, Этьен; Пасечник Дмитрий В.; Салазар, Геласио (2014), «Книжные рисунки полных двудольных графов», Discrete Applied Mathematics , 167 : 80–93, arXiv : 1210.2918 , doi : 10.1016/j.dam.2013.11.001, MR  3166108, S2CID  40920263.
20. Сперфельд, Конрад (2013), «О номере страницы полных нечетно-частных графов», Discrete Mathematics , 313 (17): 1689–1696, doi : 10.1016/j.disc.2013.04.028 , MR  3061004.
21. Хасунума, Тору; Шибата, Юкио (1997), «Вложение де Брейна, Каутца и сетей произвольного обмена в книги», Discrete Applied Mathematics , 78 (1–3): 103–116, doi : 10.1016/S0166-218X(97)00009-7 , МР  1475820; Танака, Юки; Сибата, Юкио (2010), «О номере страницы циклов, связанных с кубом», Mathematics in Computer Science , 3 (1): 109–117, doi : 10.1007/s11786-009-0012-y, MR  2596254, S2CID  11830437. См. также Обренич, Бояна (1993), «Вложение де Брейна и графики случайного обмена на пяти страницах», SIAM Journal on Discrete Mathematics , 6 (4): 642–654, doi : 10.1137/0406049, MR  1241401.
22. Бекос, Майкл А.; Гронеманн, Мартин; Рафтопулу, Хризанти Н. (2014), «Вложения 4-планарных графов в двухстраничную книгу», Труды 31-го симпозиума по теоретическим аспектам информатики , Международные труды Лейбница по информатике (LIPIcs), vol. 25, стр. 137–148, arXiv : 1401.0684 , doi : 10.4230/LIPIcs.STACS.2014.137, ISBN 9783939897651.
23. Хит, Ленни (1984), «Вложение плоских графов на семь страниц», Труды 25-го ежегодного симпозиума по основам информатики , стр. 74–83, doi : 10.1109/SFCS.1984.715903.
24. Бекос, Майкл А.; Кауфманн, Майкл; Клют, Фабиан; Пупырев, Сергей; Рафтопулу, Хризанти; Юкердт, Торстен (2020), «Для планарных графов действительно необходимы четыре страницы», Journal of Computational Geomerty , 1 (11): 332–353, arXiv : 2004.07630.
25. Эппштейн, Дэвид (2001), «Отделение геометрической толщины от толщины книги», arXiv : math.CO/0109195.
26. Дуймович, Вида ; Эппштейн, Дэвид ; Хикингботэм, Роберт; Морен, Пэт ; Вуд, Дэвид Р. (август 2021 г.), «Номер стека не ограничен номером очереди», Combinatorica , 42 (2): 151–164, arXiv : 2011.04195 , doi : 10.1007/s00493-021-4585-7, S2CID  226281691
27. Дуймович, Вида ; Вуд, Дэвид Р. (2007), «Параметры ширины дерева графика и геометрической толщины», Дискретная и вычислительная геометрия , 37 (4): 641–670, arXiv : math/0503553 , doi : 10.1007/s00454-007-1318-7, S2CID  9141367.
28. Гэнли, Джозеф Л.; Хит, Ленвуд С. (2001), «Номер страницы k -деревьев равен O ( k ) », Discrete Applied Mathematics , 109 (3): 215–221, doi : 10.1016/S0166-218X(00)00178-5 , МР  1818238.
29. Малиц, Сет М. (1994), «Графы с ребрами E имеют номер страницы O (√ E ) », Journal of Algorithms , 17 (1): 71–84, doi : 10.1006/jagm.1994.1027, MR  1279269.
30. Малиц, Сет М. (1994), «Графы рода g имеют номер страницы O (√ g ) », Journal of Algorithms , 17 (1): 85–109, doi : 10.1006/jagm.1994.1028, MR  1279270.
31. Нешетржил, Ярослав ; Оссона де Мендес, Патрис (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), «Графы ограниченной степени имеют сколь угодно большую геометрическую толщину», Electronic Journal of Combinatorics , 13 (1): R3, doi : 10.37236/1029 , MR  2200531.
36. Дуймович, Вида ; Сидиропулос, Анастасиос; Вуд, Дэвид Р. (2015), «3-монотонные расширители», arXiv : 1501.05020 [math.CO], улучшая более ранний результат, показывающий существование расширителей с постоянным номером страницы из Бургена, Жана (2009), «Расширители и размерное расширение», Comptes Rendus Mathématique , 347 (7–8): 357–362, doi : 10.1016/j.crma .2009.02.009, МР  2537230; Бурген, Жан ; Иегудайофф, Амир (2013), «Расширение и монотонные расширители», Геометрический и функциональный анализ , 23 (1): 1–41, doi : 10.1007/s00039-012-0200-9, MR  3037896, S2CID  121554827 ${\displaystyle \mathrm {SL} _{2}(\mathbb {R} )}$. См. также Галил, Цви ; Каннан, Рави ; Семереди, Эндре (1989), «О трехпозиционных графах с большими разделителями», Combinatorica , 9 (1): 9–19, doi : 10.1007/BF02122679, MR  1010295, S2CID  37506294; Двир, Зеев; Вигдерсон, Ави (2010), «Монотонные расширители: конструкции и приложения», Теория вычислений , 6 : 291–308, doi : 10.4086/toc.2010.v006a012 , MR  2770077.
37. Хит, Ленвуд С.; Розенберг, Арнольд Л. (1992), «Размещение графиков с использованием очередей», SIAM Journal on Computing , 21 (5): 927–958, doi : 10.1137/0221055, MR  1181408.
38. Дуймович, Вида ; Вуд, Дэвид Р. (2004), «О линейных схемах графов», Discrete Mathematics & Theoretical Computer Science , 6 (2): 339–357, MR  2081479.
39. https://www.math.ias.edu/avi/node/820
40. Чунг, Фан РК ; Лейтон, Фрэнк Томпсон ; Розенберг, Арнольд Л. (1987), «Вложение графиков в книги: проблема компоновки с приложениями к проектированию СБИС» (PDF) , SIAM Journal on Algebraic and Discrete Methods , 8 (1): 33–58, doi : 10.1137/0608002.
41. Унгер, Уолтер (1992), «Сложность раскраски круговых графов», STACS 92: 9-й ежегодный симпозиум по теоретическим аспектам информатики, Кашан, Франция, 13–15 февраля 1992 г., Труды , Конспекты лекций по информатике, том . 577, Берлин: Springer, стр. 389–400, номер документа : 10.1007/3-540-55210-3_199..
42. Унгер, Уолтер (1988), «О k-раскраске круговых графов», Труды 5-го симпозиума по теоретическим аспектам информатики (STACS '88) , Конспекты лекций по информатике, том. 294, Springer-Verlag, стр. 61–72, номер документа : 10.1007/BFb0035832..
43. Масуда, Сумио; Накадзима, Кадзуо; Касивабара, Тосинобу; Фудзисава, Тошио (1990), «Перекрестная минимизация в линейных вложениях графов», IEEE Transactions on Computers , 39 (1): 124–127, doi : 10.1109/12.46286, MR  1032144.
44. Гэри, MR ; Джонсон, Д.С .; Миллер, ГЛ ; Пападимитриу, CH (1980), «Сложность раскраски дуг окружностей и хорд», SIAM Journal on Algebraic and Discrete Methods , 1 (2): 216–227, doi : 10.1137/0601025, MR  0578325.
45. Хонг, Сок Хи ; Нагамоти, Хироши (2009 г.), Встраивание двухстраничной книги и планарность кластеризованных графов (PDF) , Технический отчет (изд. 2009–004 г.), Кафедра прикладной математики и физики, Университет Киото, Япония, заархивировано из оригинала (PDF) ) 24 сентября 2020 г. , получено 16 июня 2014 г..
46. Анджелини, Патрицио; Ди Бартоломео, Марко; Ди Баттиста, Джузеппе (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.
47. Нешетржил и Оссона де Мендес (2012), следствие 18.1, стр. 401.
48. Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2008), «Grad и классы с ограниченным расширением. II. Алгоритмические аспекты», European Journal of Combinatorics , 29 (3): 777–791, arXiv : math/0508324 , doi : 10.1016/j.ejc .2006.07.014, МР  2397336, S2CID  1139740.
49. Нешетржил и Оссона де Мендес (2012), Теорема 18.7, стр. 405.
50. Розенберг, Арнольд Л. (1986), «Вложения книг и интеграция в масштабе пластины», Труды семнадцатой Юго-восточной международной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1986) , Congressus Numerantium, vol. 54, стр. 217–224, МР  0885282..
51. Кнут, Дональд Э. (1968), Искусство компьютерного программирования, том. 1 , Бостон: Аддисон-Уэсли, раздел 2.2.1, упражнения 4 и 5, ISBN 0-201-89683-4, МР  0286317, OCLC  155842391.
52. Кайнен, Пол К. (1990), «Книжная толщина графа. II», Труды двадцатой Юго-восточной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1989) , Congressus Numerantium, vol. 71, стр. 127–132, МР  1041623.
53. Ваттенберг, М. (2002), «Дужные диаграммы: визуализация структуры в строках», Труды симпозиума IEEE по визуализации информации (INFOVIS 2002) , стр. 110–116, doi : 10.1109/INFVIS.2002.1173155, S2CID  881989.
54. Баур, Майкл; Брандес, Ульрик (2005), «Пересекающаяся редукция в круговых макетах», Ван Леувен, Ян (редактор), Теоретико-графовые концепции в информатике: 30-й международный семинар, WG 2004, Бад-Хоннеф, Германия, 21-23 июня, 2004, Переработанные статьи, Конспекты лекций по информатике, том. 3353, Springer, стр. 332–343, номер документа : 10.1007/978-3-540-30559-0_28..
55. Анджелини, Патрицио; Ди Баттиста, Джузеппе; Фрати, Фабрицио; Патриньяни, Маурицио; Раттер, Игнац (2012), «Проверка одновременной встраиваемости двух графов, пересечение которых является двусвязным или связным графом», Журнал дискретных алгоритмов , 14 : 150–172, doi : 10.1016/j.jda.2011.12.015 , MR  2922068.
56. Вуд, Дэвид Р. (2002), «Вложения книг с ограниченными степенями и трехмерное рисование ортогональных графов», Рисование графиков: 9-й Международный симпозиум, GD 2001, Вена, Австрия, 23–26 сентября 2001 г., Пересмотренные статьи , Лекция Заметки по информатике, том. 2265, Springer, Berlin, стр. 312–327, doi : 10.1007/3-540-45848-4_25 , MR  1962433.
57. Саати, Томас Л. (1964), «Минимальное количество пересечений в полных графах», Труды Национальной академии наук Соединенных Штатов Америки , 52 (3): 688–690, Bibcode : 1964PNAS ... 52..688S, doi : 10.1073/pnas.52.3.688 , MR  0166772, PMC 300329 , PMID  16591215 .
58. Николсон, TAJ (1968), «Процедура перестановки для минимизации количества пересечений в сети», Труды Института инженеров-электриков , 115 : 21–26, doi : 10.1049/piee.1968.0004, MR  0311416.
59. Мияучи, Мики (2006), «Топологическое вложение двудольных графов в книгу», Транзакции IEICE по основам электроники, коммуникаций и компьютерных наук , E89-A (5): 1223–1226, Бибкод : 2006IEITF..89.1223M, doi : 10.1093/ietfec/e89-a.5.1223.
60. Джордано, Франческо; Лиотта, Джузеппе; Мчедлидзе Тамара; Симвонис, Антониос (2007), «Вычисление восходящих топологических книжных вложений восходящих плоских орграфов», Алгоритмы и вычисления: 18-й Международный симпозиум, ISAAC 2007, Сендай, Япония, 17–19 декабря 2007 г., Труды , Конспекты лекций по информатике, том . 4835, Springer, стр. 172–183, номер документа : 10.1007/978-3-540-77120-3_17..
61. Он, Хунмэй; Сикора, Ондрей (2004), «Новые алгоритмы кругового рисования», Материалы семинара по информационным технологиям – приложениям и теории (ITAT), Словакия, 15–19 сентября 2004 г..
62. Шахрохи, Фархад; Сикора, Ондрей; Секели, Ласло А.; Врт'о, Имрих (1995), «Вложения книг и числа пересечений», Теоретико-графовые концепции в информатике: 20-й международный семинар, WG '94, Херршинг, Германия, 16–18 июня 1994 г., Труды , Конспекты лекций по компьютеру Наука, том. 903, Springer, стр. 256–268, номер документа : 10.1007/3-540-59071-4_53..
63. Баннистер, Майкл Дж.; Эппштейн, Дэвид ; Саймонс, Джозеф А. (2013), «Управляемость минимизации пересечений почти-деревьев с фиксированным параметром», Рисунок графика: 21-й международный симпозиум, GD 2013, Бордо, Франция, 23–25 сентября 2013 г., Пересмотренные избранные статьи , конспекты лекций в Информатика, том. 8242, стр. 340–351, arXiv : 1308.5741 , doi : 10.1007/978-3-319-03841-4_30, S2CID  10142319.
64. Баннистер, Майкл Дж.; Эппштейн, Дэвид (2014), «Перекрестная минимизация для одностраничных и двухстраничных рисунков графов с ограниченной шириной дерева», Proc. 22-й Международный Симп. Рисование графиков (GD 2014) , Конспекты лекций по информатике, том. 8871, Springer-Verlag, стр. 210–221, arXiv : 1408.6321 , doi : 10.1007/978-3-662-45803-7_18, MR  3333228.
65. Блин, Гийом; Фертен, Гийом; Русу, Ирена; Синоке, Кристина (2007), «Повышение жесткости сравнения вторичной структуры РНК», Комбинаторика, алгоритмы, вероятностные и экспериментальные методологии: Первый международный симпозиум, ESCAPE 2007, Ханчжоу, Китай, 7–9 апреля 2007 г., Пересмотренные избранные статьи (PDF) ) , Конспекты лекций по информатике, вып. 4614, стр. 140–151, номер документа : 10.1007/978-3-540-74450-4_13..
66. Клот, Питер; Добрев, Стефан; Доту, Иван; Кранакис, Евангелос; Кризанц, Дэнни; Уррутия, Хорхе (2012), «На количестве страниц вторичных структур РНК с псевдоузлами», Журнал математической биологии , 65 (6–7): 1337–1357, doi : 10.1007/s00285-011-0493-6, PMID  22159642 , S2CID  8700502.
67. Паван, А.; Тевари, Рагунатх; Винодчандран, Н.В. (2012), «О силе однозначности в лог-пространстве», Computational Complexity , 21 (4): 643–670, arXiv : 1001.2034 , doi : 10.1007/s00037-012-0047-3, MR  2988774, S2CID  8666071.
68. Галил, Цви ; Каннан, Рави ; Семереди, Эндре (1989), «О нетривиальных сепараторах для k-страничных графов и моделировании с помощью недетерминированных одноленточных машин Тьюринга», Journal of Computer and System Sciences , 38 (1): 134–149, doi : 10.1016/0022-0000 (89)90036-6.
69. Маккензи, Томас; Овербей, Шеннон (2010), «Книжные вложения и делители нуля», Ars Combinatoria , 95 : 55–63, MR  2656248.
70. Дынников И.А. (1999), «Трехстраничный подход к теории узлов. Кодирование и локальные движения», Российская академия наук , 33 (4): 25–37, 96, doi : 10.1007/BF02467109, MR  1746427, S2CID  121089736.
71. Дынников И.А. (2001), «Новый способ представления связей, одномерный формализм и технология распутывания», Acta Applicandae Mathematicae , 69 (3): 243–283, doi : 10.1023/A: 1014299416618, MR  1885279, S2CID  116488382.