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

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

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

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

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

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

История

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

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

Определения

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

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

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

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

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

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

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

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

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

${\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 },$

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

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

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

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

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

$t\leq (r-1)\left\lceil {\frac {k}{2}}\right\rceil +\left\lceil {\frac {k}{4}}\right\rceil .$

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

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

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

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

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

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

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

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

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

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

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

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

Графы древовидной ширины k имеют толщину книги не более k + 1. и эта граница узка для к > 2 . Графы с m ребрами имеют толщину книги. $O({\sqrt {m}})$, а графы рода g имеют книжную толщину $O({\sqrt {g}})$. В более общем смысле, каждое семейство второстепенных замкнутых графов имеет ограниченную толщину книги. С другой стороны, 1-планарные графы , не замкнутые относительно миноров, также ограничили толщину книги, но некоторые 1-планарные графы, включая K _2,2,2,2, имеют толщину книги не менее четырех.

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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