книжное вложение

Книжное вложение в теории графов — обобщение планарного вложения графа до вложения в книгу — набор полуплоскостей, имеющих одну и ту же прямую в качестве границы. Обычно требуется, чтобы вершины графа лежали на этой границе, а рёбра должны находиться внутри одной страницы. Книжная толщина (или число страниц) графа — наименьшее число полуплоскостей для всех книжных вложений графа. Книжное вложение используется для некоторых других инвариантов графа, включая ширину страницы и книжное число скрещиваний. Любой граф с n вершинами имеет книжную толщину максимум . Эта граница близка для полных графов. Однако подразделение каждого ребра может сократить книжную толщину к величине, пропорциональной корню квадратному из n. Графы с книжной толщиной один являются внешнепланарными графами, а графы с книжной толщиной не более двух являются подгамильтоновыми, которые всегда планарны. Любой планарный граф имеет книжную толщину, не превышающую четырёх. Все минорно замкнутые семейства графов, и, в частности, графы с ограниченной древесной шириной или ограниченным родом, также имеют ограниченную книжную толщину. Определение точной книжной толщины заданного графа является NP-трудной задачи, независимо от того, известен или нет порядок вершин на корешке. Одной из начальных поводов для изучения книжного вложения было применение его в разработке СБИС, где вершины книжного вложения представляют компоненты, а рёбра представляют соединения между компонентами.При визуализации графов два стандартных стиля представления графов, дуговые диаграммы и круговые расположения, можно построить с помощью книжного вложения.Различные начальные и конечные точки движения пешеходов и машин, которые регулируются светофором, могут быть смоделированы математически как вершины графа, а рёбра будут представлять пары начало-конец, книжное же вложение этого графа можно использовать для создания режима работы светофора, чтобы обеспечить регулировку движения с минимальным числом состояний светофора.В задачах биоинформатики, работающих со структурами РНК, одностраничное книжное вложение представляет классическую форму , а двухстраничное вложение представляет псевдоузлы.Книжное вложение используется также в общей алгебре и теории узлов. Открытыми проблемами, касающимися книжного вложения, являются * Ограничена ли книжная толщина произвольного графа функцией его подразбиений * Достаточно ли знать порядок вершин на корешке, чтобы проверить, что граф имеет трёхстраничное вложение * Существует ли планарный граф, книжная толщина которого равна четырём * Сколько пересечений на корешке необходимо для трёхстраничного топологического вложения (в этом случае рёбра могут переходить со страницы на страницу через корешок) произвольного графа.