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

Любой граф с n вершинами имеет книжную толщину максимум ${\displaystyle \lceil n/2\rceil }$. Эта граница близка для полных графов^[1]. Однако подразделение каждого ребра может сократить книжную толщину к величине, пропорциональной корню квадратному из n.^[4] Графы с книжной толщиной один являются внешнепланарными графами,^[1] а графы с книжной толщиной не более двух являются подгамильтоновыми^[en], которые всегда планарны^[2]. Любой планарный граф имеет книжную толщину, не превышающую четырёх^[5]. Все минорно замкнутые семейства графов^[en], и, в частности, графы с ограниченной древесной шириной или ограниченным родом, также имеют ограниченную книжную толщину^[6]. Определение точной книжной толщины заданного графа является NP-трудной задачи, независимо от того, известен или нет порядок вершин на корешке^[7][8].

Одной из начальных поводов для изучения книжного вложения было применение его в разработке СБИС, где вершины книжного вложения представляют компоненты, а рёбра представляют соединения между компонентами^[7][9]. При визуализации графов два стандартных стиля представления графов, дуговые диаграммы^[en][10] и круговые размещения^[en][11], можно построить с помощью книжного вложения. Различные начальные и конечные точки движения пешеходов и машин, которые регулируются светофором, могут быть смоделированы математически как вершины графа, а рёбра будут представлять пары начало-конец, книжное же вложение этого графа можно использовать для создания режима работы светофора, чтобы обеспечить регулировку движения с минимальным числом состояний светофора^[12]. В задачах биоинформатики, работающих со структурами РНК, одностраничное книжное вложение представляет классическую форму вторичной структуры нуклеиновой кислоты^[en], а двухстраничное вложение представляет псевдоузлы^[13]. Книжное вложение используется также в общей алгебре^[14] и теории узлов. ^[15][16]

Открытыми проблемами, касающимися книжного вложения, являются

• Ограничена ли книжная толщина произвольного графа функцией его подразбиений^[en][17]
• Достаточно ли знать порядок вершин на корешке, чтобы проверить, что граф имеет трёхстраничное вложение^[18]
• Существует ли планарный граф, книжная толщина которого равна четырём^[19]
• Сколько пересечений на корешке необходимо для трёхстраничного топологического вложения (в этом случае рёбра могут переходить со страницы на страницу через корешок) произвольного графа^[20].

История

Название «книга» было введено Персингером и Атнеосеном (C.A. Persinger, Gail Atneosen) в 1960-е годы^[21][22]. Атнеосен уже использовал вложение графов в книги, но формальная концепция книжного вложения была сформулирована Кайненом и Оллманом (C. Kainen, L. Taylor Ollman) в начале 1970-х и были добавлены некоторые дополнительные ограничения на способ вложения — в их формулировке вершины графа должны лежать на корешке книги, каждое ребро должно лежать на одной странице (не пересекать корешок) и любые два ребра пересекаются только в общих конечных вершинах^{[23] [24]}.

Важными вехами в дальнейшем развитии книжного вложения является доказательство Михалисом Яннакакисом в конце 1980-х, что книжная толщина планарных графов не превосходит четырёх^[25][5], и открытие в конце 1990-х тесной связи между книжным вложением и биоинформатикой.^[13]

Определения

Книга является частным видом топологического пространства (называемого также веером^[en] полуплоскостей)^[21][26]. Оно состоит из одной прямой ℓ, называемой корешком^[27] книги, вместе с набором одной или более полуплоскостей, называемых страницами или листами книги. Каждая полуплоскость должна иметь одну и ту же прямую ℓ в качестве границы. Книги с конечным числом (k) страниц могут быть вложены в трёхмерное пространство, например, посредством выбора в качестве прямой ℓ оси z прямоугольной системы координат, а в качестве i-ой страницы (из k) можно взять множество точек p, таких что кратчайший отрезок, соединяющий p с осью z, имеет угол 2πi/k по отношению к плоскости xz^[1].

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

Книжное вложение графа G в B — это вложение графа G в пространство B. То есть это рисунок графа G в B, при котором рёбра не пересекаются. Любой конечный граф имеет книжное вложение в книгу с достаточно большим числом страниц. Например, всегда есть возможность вложить каждое ребро на свою собственную страницу. Толщина книги, число страниц, или стэковое число графа G — это минимальное число страниц, которое требуется для книжного вложения графа G. Другой параметр, измеряющий качество книжного вложения, кроме числа страниц, — это ширина страницы. Это максимальное число рёбер, которое пересекает луч, перпендикулярный корешку внутри отдельной страницы. Эквивалентно (для книжных вложений, в которых каждое ребро нарисовано как монотонная кривая), это максимальный размер подмножества рёбер, таких что интервалы, определённые на корешке конечными точками рёбер, все пересекаются^[2][28][29].

Существенно для этих определений, что рёбра могут лежать только на одной странице. Как заметил уже Амеозен, если рёбра могут переходить со страницы на страницу (через корешок), то любой граф можно вложить в трёхстраничную книгу^[22][30][20]. Однако для трёхстраничного топологического книжного вложения, в котором пересечение корешка разрешено, остаётся интересной задача определения наименьшего числа пресечения корешка, позволяющего вложить граф в книгу^{[20] [31]}.

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

Как показано на первом рисунке, книжная толщина полного графа ${\displaystyle K_{5}}$ равна трём. Поскольку он непланарен, его книжная толщина больше двух, но существует книжное вложение с тремя страницами. Книжная толщина любого полного графа с ${\displaystyle n\geq 4}$ вершинами равна в точности ${\displaystyle \lceil n/2\rceil }$. Этот результат даёт верхнюю границу^[en] максимальной книжной толщины любых графов с ${\displaystyle n}$ вершинами^[1]. Двухстраничное число пересечений полного графа ${\displaystyle K_{n}}$ равно

${\displaystyle (1/4)\left\lfloor {\frac {n}{2}}\right\rfloor \left\lfloor {\frac {n-1}{2}}\right\rfloor \left\lfloor {\frac {n-2}{2}}\right\rfloor \left\lfloor {\frac {n-3}{2}}\right\rfloor ,}$

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

Толщина книги полного двудольного графа ${\displaystyle K_{a,b}}$ почти равна ${\displaystyle \min\{a,b\}}$ — для каждой вершины меньшей доли можно расположить рёбра, инцидентные этим вершинам, на собственной странице. Эта граница не всегда строгая. Например, ${\displaystyle K_{4,4}}$ имеет толщину книги три, а не четыре. Однако, когда две стороны графа сильно разбалансированы, с ${\displaystyle b>a(a-1)}$, толщина книги ${\displaystyle K_{a,b}}$ равна в точности ${\displaystyle a}$.^[1][33] Толщина книг двоичных графов де Брёйна, графов тасованного обмена, и кубических сетей с циклами^[en] (когда эти графы достаточно велики, чтобы не быть планарными) равна в точности трём.^[34]

Свойства

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

Разбиение^[en] каждого ребра графа на двухрёберные пути путём добавления новых вершин для каждого ребра может иногда увеличить толщину книги (например, алмаз^[en] имеет книжную толщину один, но его подразбиение имеет книжную толщину два). Однако такое подразбиение может также существенно уменьшить книжную толщину графа после разбиения. Например, книжная толщина полного графа K_n is Θ(n) пропорциональна числу его вершин, но разбиение каждого ребра на два даёт подразбиение с много меньшей книжной толщиной, лишь O(√n).^[4]. Несмотря на существование примеров, подобных вышеприведённому, Бланкеншип и Опоровски^[30] высказали гипотезу, что книжная толщина подразбиений не может быть существенно меньше, чем у исходного графа. В частности, они предположили, что существует некая функция f, что для любого графа G и графа H, полученного заменой каждого ребра G путём из двух рёбер, если книжная толщина графа H равна t, то книжная толщина графа G не превышает f(t).^[30] К 2013 гипотеза Бланкеншипа–Опоровски оставалась недоказанной.^[17]

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

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

Любое книжное вложение с двумя страницами является специальным случаем планарного вложения, поскольку объединение двух страниц книги является пространством, топологически эквивалентным плоскости. Таким образом, любой граф с книжной толщиной два автоматически является планарным. Точнее, книжная толщина графа G не больше двух тогда и только тогда, когда G является подграфом планарного графа, который имеет гамильтонов цикл^[1]. Если дан граф с книжным вложением в две страницы, граф может быть расширен до планарного гамильтонова графа путём добавления (на любой странице) дополнительных рёбер между любыми двумя последовательными вершинами вдоль корешка, если они ещё не соединены ребром, а также между первой и последней вершиной корешка. Граф Голднера–Харари даёт пример планарного графа, не имеющего книжной толщины два — это максимальный планарный граф^[en], так что невозможно добавить никакое ребро, сохраняя планарность, и граф не имеет гамильтонова цикла^[1]. Ввиду требования наличия гамильтоновых циклов графы, позволяющие двухстраничное вложение, известны как подгамильтоновы графы^[en][2].

Все планарные графы с максимальной степенью, не превышающей четырёх, имеют толщину книжного вложения, не превышающую двух.^[35]. Планарные 3-деревья^[en] имеют максимальную толщину книги, равную трём^[36]. Все планарные графы имеют книжную толщину, не превышающую четырёх^[25][5]. Как утверждал Михалис Яннакакис в 1986^[25], существуют планарные графы с толщиной книжного вложения, в точности равной четырём, однако детальное доказательство этого утверждения, анонсированного в статье^[5], так и не было опубликовано. По этой причине Дуймович^[19] обозначил задачу определения максимальной толщины книжного вложения планарных графов как нерешённую^[19].

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

Толщина книги связана с толщиной графа, числом планарных графов, которые необходимы для покрытия рёбер заданного графа. Граф G имеет толщину θ, если его можно вложить в плоскость, и при этом рёбра можно раскрасить в θ цветов таким образом, что рёбра одного цвета не пересекаются. Аналогично граф G имеет книжную толщину θ, если его можно нарисовать в полуплоскости с вершинами на границе полуплоскости и раскрасить рёбра в θ цветов без пересечений рёбер одного цвета. При такой формулировке рёбра одного цвета соответствуют страницам книжного вложения. Однако толщина графа и толщина книги могут существенно различаться — существуют подразделения^[en] полных графов, имеющие неограниченную книжную толщину^[30][20][4], несмотря на то, что толщина графа равна двум^[4].

Графы с древесной шириной k имеют книжную толщину, не превосходящую k + 1^[19][37] и эта граница достигается для k > 2.^[19]. Графы с m рёбрами имеют книжную толщину O(√m)^[38], а графы с родом g — книжную толщину O(√g)^[39]. Более обще, любое минорно-замкнутое семейство графов^[en] имеет ограниченную книжную толщину^[6][40].

Любой стягивающий минор^[en] графа ограниченной книжной толщины является разреженным графом, у которого отношение рёбер к вершинам ограничено константной, которая зависит только от глубины минора и книжной толщины. То есть, в терминологии Нешетрила^[6], графы с ограниченной книжной толщиной имеют ограниченный рост^[6]. Однако даже графы с ограниченной степенью графа существенно более сильное требование ограничения роста, может иметь неограниченную книжную толщину^[41].

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

Рёбра на одной странице книжного вложения ведут себя подобно стеку. Это можно формализовать, если рассмотреть произвольную последовательность операций push и pop (засылка и извлечение) на стеке и сформировать граф, в котором стековые операции соответствуют вершинам графа, расположенным на корешке книжного вложения в порядке выполнения операций. Если теперь нарисовать ребро от каждой операции pop, извлекающей объект x из стека к операции push, заславшей этот элемент в стек, полученный граф будет иметь автоматически одностраничное вложение. По этой причине число страниц графа называют также его стековым числом. По аналогии исследователи определяют очередное вложение графа как рисунок графа в книге, в котором любые два ребра на странице либо пересекаются, либо покрывают непересекающиеся интервалы на корешке. Такие вложения соответствуют некоторым образом очередям и минимальное число страниц, необходимых для очередного вложения графа, называется его очередным числом^[en].^[6][43][44]

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

Определение толщины книжного вложения является NP-трудной задачей. Это следует из факта, что нахождение гамильтонова цикла в максимальных планарных графах является NP-полной задачей. Толщина книжного вложения максимального планарного графа равна двум тогда и только тогда, когда гамильтонов путь существует. Поэтому определение, что толщина книжного вложения заданного максимального планарного графа равна двум, также является NP-полной задачей.^[7]

Если порядок расположения вершин вдоль корешка при книжном вложении предопределён, двухстраничное вложение (если такое существует) может быть найдено за линейное время как вариант проверки планарности^[en] для графа, полученного расширением заданного графа путём создания цикла, соединяющего вершины вдоль корешка^[13]. Унгер утверждал, что нахождение трёхстраничного вложения с предопределённым порядком вершин может быть осуществлено за полиномиальное время, хотя в его описании этого результата отсутствует ряд существенных деталей^[18]. Однако для графов, которые требуют четыре и более страниц, задача нахождения вложения с минимально возможным числом страниц остаётся NP-трудной ввиду эквивалентности NP-трудной задаче раскраски круговых графов^[en], графов пересечений хорд окружности. Если задан граф G с фиксированным порядком вершин на корешке, расположение этих вершин в том же порядке на окружности и представление рёбер графа G в виде отрезков даёт набор хорд, представляющих граф G. Можно теперь образовать круговой граф^[en], имеющий хорды этой диаграммы в качестве вершин, а пересекающиеся пары хорд в качестве рёбер. Раскраска кругового графа^[en] даёт разбиение рёбер графа G на подмножества, которые могут быть нарисованы без пересечений на одной странице. Таким образом, оптимальная раскраска эквивалентна оптимальному книжному вложению. Поскольку раскраска кругового графа^[en] в четыре и более цветов является NP-трудной задачей, и поскольку любой круговой граф^[en] может быть образован таким образом из некоторой задачи нахождения книжного вложения, нахождение оптимального книжного вложения является также NP-трудной задачей^[8][45][46]. Для фиксированного порядка вершин на корешке при двухстраничном вложении является NP-трудной задачей минимизация числа пересечений, если это число не равно нулю^[45].

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

Задача изоморфизма подграфа^[en], заключающаяся в определении, находится ли ограниченный в размере граф некоторого вида в качестве подграфа большего графа, может быть решена за линейное время, если больший граф имеет ограниченную толщину книжного вложения. То же самое верно и для определения, является ли граф некоторого вида порождённым подграфом большего графа, или он имеет гомеоморфизм^[en] с большим графом^[49][50]. По той же причине задача проверки, удовлетворяет ли граф с ограниченной книжной толщиной заданной формуле логики первого порядка, является разрешимой относительно фиксированного параметра^[en][51].

Приложения

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

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

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

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

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

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

Визуализация графов

Книжное вложение часто применяется также для визуализации сетевого потока данных. Две стандартных схемы визуализации графов, дуговые диаграммы^[10] и круговые диаграммы^[11], можно рассматривать как книжные вложения. Книжное вложение можно использовать также для построения кластерных схем^[47], одновременных вложений^[53] и трёхмерных рисунков графов^[54].

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

При другом стиле рисования, круговой схеме^[en], вершины графа располагаются на окружности, а рёбра рисуются внутри или снаружи окружности^[11]. Снова расположение рёбер внутри окружности (например, как отрезки) соответствуют одностраничному книжному рисованию, в то время как расположение рёбер по обе стороны от окружности соответствует двухстраничному книжному рисованию^[59].

Для одностраничных рисований любого стиля важно сохранять число пересечений малым, чтобы уменьшить визуальный хаос рисунка. Минимизация числа пересечений является NP-полной задачей^[45], но задача может быть аппроксимирована с отношением O(log² n), где n является числом вершин^[60]. Минимизация одностраничного или двухстраничного числа пересечений является разрешимой относительно фиксированного параметра^[en], когда параметризуется цикломатическим числом^[en] заданного графа^[61]. Разрабатывались также эвристические методы уменьшения сложности пересечений, основанные, например, на аккуратном порядке вставки вершин и на локальной оптимизации^[11].

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

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

Фолдинг РНК

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

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

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

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

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

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

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

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

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

Примечания