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

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

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

В теории графов книжное вложение — это обобщение планарного вложения графа на вложения в книгу , набор полуплоскостей, имеющих одну и ту же линию в качестве границы. Обычно вершины графа должны лежать на этой граничной линии, называемой позвоночником , а ребра должны оставаться в пределах одной полуплоскости. Книжная толщина графа — это наименьшее возможное число полуплоскостей для любого книжного вложения графа. Книжная толщина также называется pagenumber , stacknumber или fixed externalthickness . Книжные вложения также использовались для определения нескольких других инвариантов графа, включая pagewidth и book crossing number.

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

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

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

История

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

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

Определения

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

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

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

Рисунок книги конечного графа G на книге B — это рисунок G на B, такой , что каждая вершина G нарисована как точка на корешке B , а каждое ребро G нарисовано как кривая , которая лежит в пределах одной страницы B. Число пересечений книги на 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 ) . Чтобы построить рисунок с такой толщиной книги, для каждой вершины на меньшей стороне двудольного графа можно разместить ребра, инцидентные этой вершине, на их собственной странице. Эта граница не всегда строгая; например, K _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]} Однако доказательство этого утверждения опирается на предыдущее утверждение о том, что графы, вложенные в неориентируемые поверхности, имеют ограниченную книжную толщину, для которого подробное доказательство не было предоставлено. ^[33] 1-планарные графы , которые не замкнуты относительно миноров, ^[31] имеют ограниченную книжную толщину, ^[34] но некоторые 1-планарные графы, включая K _2,2,2,2, имеют книжную толщину не менее четырех. ^[35] ${\displaystyle O({\sqrt {m}})}$ ${\displaystyle O({\sqrt {g}})}$

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

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

Управление дорожным движением

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

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

Графическое изображение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

1. Persinger, CA (1966), "Подмножества n -книг в E ³ ", Pacific Journal of Mathematics , 18 : 169–173, doi : 10.2140/pjm.1966.18.169 , MR  0195077.
2. Atneosen, Gail Adele (1968), О вложимости компактов в n-книги: внутренние и внешние свойства, докторская диссертация, Мичиганский государственный университет , стр. 79, MR  2617705. См. также Атнеосен, Гейл Х. (1972), «Одномерные n-листные континуумы» (PDF) , Fundamenta Mathematicae , 74 (1): 43–45, doi : 10.4064/fm-74-1-43-45 , МР  0293592.
3. Kainen, Paul C. (1974), «Некоторые недавние результаты в топологической теории графов», в Bari, Ruth A.; Harary, Frank (ред.), Graphs and Combinatorics (Труды конференции Capital Conference on Graph Theory and Combinatorics at the George Washington University 18–22 июня 1973 г.) , Lecture Notes in Mathematics, т. 406, стр. 76–108.
4. Оллманн, Л. Тейлор (1973), «О толщине различных графов», в Хоффман, Фредерик; Левоу, Рой Б.; Томас, Роберт SD (ред.), Труды 4-й Юго-восточной конференции по комбинаторике, теории графов и вычислениям , Congressus Numerantium, т. 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, PMC 7197269 , PMID  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. Stöhr, Елена (1988), «Компромисс между номером страницы и шириной страницы книжных вложений графов», Information and Computation , 79 (2): 155–162, doi : 10.1016/0890-5401(88)90036-3 , MR  0968104.
14. Stöhr, Елена (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/S0895480195280319, MR  1710241.
16. Бланкеншип, Робин; Опоровски, Богдан (1999), Рисование подразделений полных и полных двудольных графов на книгах , Технический отчет 1999-4, Кафедра математики, Университет штата Луизиана, CiteSeerX 10.1.1.36.4358 .
17. Эномото, Хикоэ; Мияучи, Мики Шимабара; Ота, Кацухиро (1999), «Нижние оценки для числа пересечений ребер на позвоночнике в топологическом книжном вложении графа», Дискретная прикладная математика , 92 (2–3): 149–155, doi : 10.1016/S0166-218X(99)00044-X , MR  1697548.
18. Абрего, Бернардо М.; Айхольцер, Освин; Фернандес-Мерчант, Сильвия; Рамос, Педро; Салазар, Геласио (2012), «2-страничное число пересечений K _n (расширенный реферат)», Труды 28-го ежегодного симпозиума по вычислительной геометрии (SCG'12) , ACM, Нью-Йорк, стр. 397–403, doi :10.1145/2261250.2261310, MR  3050657, S2CID  8344088.
19. Для дополнительных результатов о толщине книги полных двудольных графов см. Enomoto, Hikoe; Nakamigawa, Tomoki; Ota, Katsuhiro (1997), "On the pagenumber of complete bipartite graphs", Journal of Combinatori Theory , Series B, 71 (1): 111–120, doi : 10.1006/jctb.1997.1773 , MR  1469870; де Клерк, Этьен; Пасечник, Дмитрий В.; Салазар, Геласио (2014), "Книжные рисунки полных двудольных графов", Дискретная прикладная математика , 167 : 80–93, arXiv : 1210.2918 , doi : 10.1016/j.dam.2013.11.001, MR  3166108, S2CID  40920263.
20. Сперфельд, Конрад (2013), «О числе страниц полных нечетно-дольных графов», Дискретная математика , 313 (17): 1689–1696, doi : 10.1016/j.disc.2013.04.028 , MR  3061004.
21. Хасунума, Тору; Шибата, Юкио (1997), «Внедрение сетей де Брейна, Каутца и тасовочно-обменных сетей в книги», Дискретная прикладная математика , 78 (1–3): 103–116, doi : 10.1016/S0166-218X(97)00009-7 , MR  1475820; Танака, Юки; Шибата, Юкио (2010), «О номере страницы кубически-связанных циклов», Математика в информатике , 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), т. 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, ISBN 0-8186-0591-X.
24. Bekos, Michael A.; Kaufmann, Micheal; Klute, Fabian; Pupyrev, Sergey; Raftopoulou, Chrysanthi; Ueckerdt, Torsten (2020), «Для планарных графов действительно необходимы четыре страницы», Journal of Computational Geomerty , 1 (11): 332–353, arXiv : 2004.07630.
25. Эппштейн, Дэвид (2001), «Отделение геометрической толщины от толщины книги», arXiv : math.CO/0109195{{cite arXiv}}: CS1 maint: переопределенная настройка ( ссылка ).
26. Дуймович, Вида ; Эппштейн, Дэвид ; Хикингботам, Роберт; Морин, Пэт ; Вуд, Дэвид Р. (август 2021 г.), «Число стека не ограничено числом очереди», Combinatorica , 42 (2): 151–164, arXiv : 2011.04195 , doi : 10.1007/s00493-021-4585-7, S2CID  226281691
27. Dujmović, Vida ; Wood, David R. (2007), «Параметры ширины дерева графа и геометрической толщины», Discrete and Computational Geometry , 37 (4): 641–670, arXiv : math/0503553 , doi :10.1007/s00454-007-1318-7, S2CID  9141367.
28. Ganley, Joseph L.; Heath, Lenwood S. (2001), "The pagenumber of k -trees is O ( k ) ", Discrete Applied Mathematics , 109 (3): 215–221, doi : 10.1016/S0166-218X(00)00178-5 , MR  1818238.
29. Малиц, Сет М. (1994), «Графы с E ребрами имеют номер страницы O (√ E ) », Журнал алгоритмов , 17 (1): 71–84, doi :10.1006/jagm.1994.1027, MR  1279269.
30. Малиц, Сет М. (1994), « Графы рода g имеют номер страницы O (√ g ) », Журнал алгоритмов , 17 (1): 85–109, doi :10.1006/jagm.1994.1028, MR  1279270.
31. Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, т. 28, Springer, стр. 321–328, doi :10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, МР  2920058.
32. Бланкеншип, Р. (2003), Книга Вложения графов , докторская диссертация, кафедра математики, Университет штата Луизиана. Цитируется Нешетрилом и Оссона де Мендес (2012).
33. Озэки, Кента; Накамото, Ацухиро; Нодзава, Такаюки (2019), «Книга по встраиванию графов на проективную плоскость» (PDF) , SIAM Journal on Discrete Mathematics , 33 (4): 1801–1836, doi : 10.1137/16M1076174, MR  4013917
34. Бекос, Майкл А.; Брукдорфер, Тилл; Кауфманн, Майкл; Рафтопулу, Хрисанти (2015), «1-Планарные графы имеют постоянную толщину книги», Алгоритмы – ESA 2015 , Lecture Notes in Computer Science, т. 9294, Springer, стр. 130–141, doi :10.1007/978-3-662-48350-3_12, ISBN 978-3-662-48349-7.
35. Bekos, Michael; Kaufmann, Michael; Zielke, Christian (2015), «Проблема вложения книг с точки зрения решения SAT», Proc. 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015) , стр. 113–125.
36. Барат, Янош; Матоушек, Йиржи ; Вуд, Дэвид Р. (2006), «Графы ограниченной степени имеют произвольно большую геометрическую толщину», Electronic Journal of Combinatorics , 13 (1): R3, doi : 10.37236/1029 , MR  2200531.
37. Дуймович, Вида ; Сидиропулос, Анастасиос; Вуд, Дэвид Р. (2015), «3-монотонные расширители», arXiv : 1501.05020 [math.CO]{{cite arXiv}}: CS1 maint: переопределенная настройка ( ссылка ), улучшая более ранний результат, показывающий существование расширителей с постоянным номером страницы из Bourgain, Jean (2009), "Expanders and dimensional extension", Comptes Rendus Mathématique , 347 (7–8): 357–362, doi :10.1016/j.crma.2009.02.009, MR  2537230; Бургейн, Жан ; Йехудайофф, Амир (2013), «Разложение в и монотонные экспандеры», Геометрический и функциональный анализ , 23 (1): 1–41, doi :10.1007/s00039-012-0200-9, MR  3037896, S2CID  121554827 ${\displaystyle \mathrm {SL} _{2}(\mathbb {R} )}$. См. также Галил, Цви ; Каннан, Рави ; Семереди, Эндре (1989), "О 3-pushdown-графах с большими сепараторами", 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.
38. Хит, Ленвуд С.; Розенберг, Арнольд Л. (1992), «Размещение графов с использованием очередей», SIAM Journal on Computing , 21 (5): 927–958, doi :10.1137/0221055, MR  1181408.
39. Дуймович, Вида ; Вуд, Дэвид Р. (2004), «О линейных макетах графов», Дискретная математика и теоретическая информатика , 6 (2): 339–357, MR  2081479.
40. Вигдерсон, Ави (февраль 1982 г.), Сложность задачи гамильтоновой цепи для максимальных планарных графов (технический отчет № 298), кафедра EECS, Принстонский университет – через Институт перспективных исследований
41. Chung, Fan RK ; Leighton, Frank Thompson ; Rosenberg, Arnold L. (1987), «Встраивание графов в книги: проблема компоновки с приложениями к проектированию СБИС» (PDF) , SIAM Journal on Algebraic and Discrete Methods , 8 (1): 33–58, doi :10.1137/0608002.
42. Унгер, Вальтер (1992), «Сложность раскраски круговых графов», STACS 92: 9-й ежегодный симпозиум по теоретическим аспектам компьютерной науки, Кашан, Франция, 13–15 февраля 1992 г., Труды , Lecture Notes in Computer Science, т. 577, Берлин: Springer, стр. 389–400, doi :10.1007/3-540-55210-3_199, ISBN 978-3-540-55210-9.
43. Унгер, Вальтер (1988), «О k-раскраске круговых графов», Труды 5-го симпозиума по теоретическим аспектам компьютерной науки (STACS '88) , Lecture Notes in Computer Science, т. 294, Springer-Verlag, стр. 61–72, doi :10.1007/BFb0035832, ISBN 3-540-18834-7.
44. Масуда, Сумио; Накадзима, Казуо; Кашивабара, Тосинобу; Фудзисава, Тосио (1990), «Минимизация перекрестков в линейных вложениях графов», IEEE Transactions on Computers , 39 (1): 124–127, doi :10.1109/12.46286, MR  1032144.
45. Garey, MR ; Johnson, DS ; Miller, GL ; Papadimitriou, CH (1980), «Сложность раскраски дуг окружностей и хорд», SIAM Journal on Algebraic and Discrete Methods , 1 (2): 216–227, doi :10.1137/0601025, MR  0578325.
46. Hong, Seok-Hee ; Nagamochi, Hiroshi (2009), Двухстраничное вложение книг и кластеризованная планарность графов (PDF) , Технический отчет (ред. 2009-004), Кафедра прикладной математики и физики, Университет Киото, Япония, архивировано из оригинала (PDF) 24.09.2020 , извлечено 16.06.2014.
47. Анджелини, Патрицио; Ди Бартоломео, Марко; Ди Баттиста, Джузеппе (2013), «Реализация алгоритма тестирования встраивания секционированной 2-страничной книги», Graph Drawing: 20th International Symposium, GD 2012, Редмонд, Вашингтон, США, 19–21 сентября 2012 г., Revised Selected Papers , Lecture Notes in Computer Science, т. 7704, Springer, стр. 79–89, arXiv : 1209.0598 , doi : 10.1007/978-3-642-36763-2_8, ISBN 978-3-642-36762-5, MR  3067219, S2CID  15360191.
48. Нешетржил и Оссона де Мендес (2012), следствие 18.1, с. 401.
49. Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2008), «Град и классы с ограниченным расширением. II. Алгоритмические аспекты», Европейский журнал комбинаторики , 29 (3): 777–791, arXiv : math/0508324 , doi :10.1016/j.ejc.2006.07.014, MR  2397336, S2CID  1139740.
50. Нешетржил и Оссона де Мендес (2012), Теорема 18.7, стр. 405.
51. Розенберг, Арнольд Л. (1986), «Вложения книг и интеграция в масштабе пластин», Труды семнадцатой Юго-Восточной международной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1986) , Congressus Numerantium, т. 54, стр. 217–224, MR  0885282.
52. Кнут, Дональд Э. (1968), Искусство программирования компьютеров. Том 1 , Бостон: Addison-Wesley, Раздел 2.2.1, Упражнения 4 и 5, ISBN 0-201-89683-4, MR  0286317, OCLC  155842391.
53. Kainen, Paul C. (1990), «Книжная толщина графа. II», Труды двадцатой Юго-Восточной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1989) , Congressus Numerantium, т. 71, стр. 127–132, MR  1041623.
54. Wattenberg, M. (2002), «Дужные диаграммы: визуализация структуры в строках», Труды симпозиума IEEE по визуализации информации (INFOVIS 2002) , стр. 110–116, doi :10.1109/INFVIS.2002.1173155, ISBN 0-7695-1751-X, S2CID  881989.
55. Baur, Michael; Brandes, Ulrik (2005), "Crossing reduction in circular layouts", в van Leeuwen, Jan (ред.), Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers, Lecture Notes in Computer Science, т. 3353, Springer, стр. 332–343, doi :10.1007/978-3-540-30559-0_28, ISBN 978-3-540-24132-4.
56. Angelini, Patrizio; Di Battista, Giuseppe; Frati, Fabrizio; Patrignani, Maurizio; Rutter, Ignaz (2012), «Проверка одновременной вложимости двух графов, пересечение которых является двусвязным или связным графом», Journal of Discrete Algorithms , 14 : 150–172, doi : 10.1016/j.jda.2011.12.015 , MR  2922068.
57. Wood, David R. (2002), "Bounded degree book embeddings and three-dimensional orthogonal graph drawing", Graph Drawing: 9th International Symposium, GD 2001, Vienna, Austria, September 23–26, 2001, Revised Papers , Lecture Notes in Computer Science, vol. 2265, Springer, Berlin, pp. 312–327, doi : 10.1007/3-540-45848-4_25 , ISBN 978-3-540-43309-5, г-н  1962433.
58. Саати, Томас Л. (1964), «Минимальное число пересечений в полных графах», Труды Национальной академии наук Соединенных Штатов Америки , 52 (3): 688–690, Bibcode : 1964PNAS...52..688S, doi : 10.1073/pnas.52.3.688 , MR  0166772, PMC 300329 , PMID  16591215 .
59. Николсон, TAJ (1968), «Процедура перестановки для минимизации числа пересечений в сети», Труды Института инженеров-электриков , 115 : 21–26, doi :10.1049/piee.1968.0004, MR  0311416.
60. Мияучи, Мики (2006), «Топологическое книжное вложение двудольных графов», IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences , E89-A (5): 1223–1226, Bibcode : 2006IEITF..89.1223M, doi : 10.1093/ietfec/e89-a.5.1223.
61. Джордано, Франческо; Лиотта, Джузеппе; Мчедлидзе, Тамара; Симвонис, Антониос (2007), «Вычисление восходящих топологических книжных вложений восходящих планарных орграфов», Алгоритмы и вычисления: 18-й международный симпозиум, ISAAC 2007, Сендай, Япония, 17–19 декабря 2007 г., Труды , Lecture Notes in Computer Science, т. 4835, Springer, стр. 172–183, doi :10.1007/978-3-540-77120-3_17, ISBN 978-3-540-77118-0.
62. Хе, Хонгмей; Сикора, Ондрей (2004), «Новые алгоритмы кругового рисования», Труды семинара по информационным технологиям – приложения и теория (ITAT), Словакия, 15–19 сентября 2004 г..
63. Shahrokhi, Farhad; Sýkora, Ondrej; Székely, László A.; Vrt'o, Imrich (1995), "Book embeddings and crossing numbers", Graph-Theoretic Concepts in Computer Science: 20th International Workshop, WG '94, Herrsching, Germany, June 16–18, 1994, Proceedings , Lecture Notes in Computer Science, vol. 903, Springer, pp. 256–268, doi :10.1007/3-540-59071-4_53, ISBN 978-3-540-59071-2.
64. Баннистер, Майкл Дж.; Эппштейн, Дэвид ; Саймонс, Джозеф А. (2013), "Fixed Parameter tractability of crossing minimization of Almost-trees", Рисование графов: 21-й международный симпозиум, GD 2013, Бордо, Франция, 23–25 сентября 2013 г., Пересмотренные избранные статьи , Заметки лекций по информатике, т. 8242, стр. 340–351, arXiv : 1308.5741 , doi : 10.1007/978-3-319-03841-4_30, ISBN 978-3-319-03840-7, S2CID  10142319.
65. Баннистер, Майкл Дж.; Эппштейн, Дэвид (2014), «Минимизация скрещивания для одностраничных и двухстраничных рисунков графов с ограниченной древовидной шириной», Proc. 22nd Int. Symp. Graph Drawing (GD 2014) , Lecture Notes in Computer Science, т. 8871, Springer-Verlag, стр. 210–221, arXiv : 1408.6321 , doi :10.1007/978-3-662-45803-7_18, ISBN 978-3-319-12567-1, г-н  3333228.
66. Блин, Гийом; Фертин, Гийом; Русу, Ирена; Синоке, Кристин (2007), «Расширение жесткости сравнения вторичной структуры РНК», Комбинаторика, алгоритмы, вероятностные и экспериментальные методологии: Первый международный симпозиум, ESCAPE 2007, Ханчжоу, Китай, 7-9 апреля 2007 г., Пересмотренные избранные статьи (PDF) , Lecture Notes in Computer Science, т. 4614, стр. 140–151, doi :10.1007/978-3-540-74450-4_13, ISBN 978-3-540-74449-8.
67. Клоте, Питер; Добрев, Стефан; Доту, Иван; Кранакис, Евангелос; Кризанц, Дэнни; ​​Уррутия, Хорхе (2012), «О номере страницы вторичных структур РНК с псевдоузлами», Журнал математической биологии , 65 (6–7): 1337–1357, doi :10.1007/s00285-011-0493-6, PMID  22159642, S2CID  8700502.
68. Паван, А.; Тевари, Рагхунат; Винодчандран, Н.В. (2012), «О силе однозначности в логарифмическом пространстве», Computational Complexity , 21 (4): 643–670, arXiv : 1001.2034 , doi : 10.1007/s00037-012-0047-3, MR  2988774, S2CID  8666071.
69. Галил, Цви ; Каннан, Рави ; Семереди, Эндре (1989), «О нетривиальных сепараторах для графов размером k страниц и моделировании с помощью недетерминированных одноленточных машин Тьюринга», Журнал компьютерных и системных наук , 38 (1): 134–149, doi : 10.1016/0022-0000(89)90036-6.
70. Маккензи, Томас; Овербей, Шеннон (2010), «Книжные вложения и делители нуля», Ars Combinatoria , 95 : 55–63, MR  2656248.
71. Дынников, И.А. (1999), «Трехстраничный подход к теории узлов. Кодирование и локальные движения», Российская академия наук , 33 (4): 25–37, 96, doi :10.1007/BF02467109, MR  1746427, S2CID  121089736.
72. Дынников, И.А. (2001), «Новый способ представления связей, одномерный формализм и технология распутывания», Acta Applicandae Mathematicae , 69 (3): 243–283, doi :10.1023/A:1014299416618, MR  1885279, S2CID  116488382.