Book embedding
http://dbpedia.org/resource/Book_embedding
In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings into a book, a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, called the spine, and the edges are required to stay within a single half-plane. The book thickness of a graph is the smallest possible number of half-planes for any book embedding of the graph. Book thickness is also called pagenumber, stacknumber or fixed outerthickness. Book embeddings have also been used to define several other graph invariants including the pagewidth and book crossing number.
rdf:langString
En teoría de grafos, un embebido en libro es una generalización del embebido plano de un grafo a embebidos en un libro, una colección de semiespacios, todos con la misma recta como límite. Por lo general, se requiere que los vértices del grafo se encuentren en esta línea límite, llamada "columna vertebral", y se requiere que los vínculos permanezcan dentro de un solo semiplano. El espesor del libro de un grafo es el número más pequeño posible de semiplanos para cualquier embebido en libro del grafo. El grosor del libro también se denomina número de páginas, número de pila o grosor exterior fijo. Los embebidos en libro también se han utilizado para definir varios otros , incluido el ancho de página y el número de cruces del libro.
rdf:langString
Книжное вложение в теории графов — обобщение планарного вложения графа до вложения в книгу — набор полуплоскостей, имеющих одну и ту же прямую в качестве границы. Обычно требуется, чтобы вершины графа лежали на этой границе, а рёбра должны находиться внутри одной страницы. Книжная толщина (или число страниц) графа — наименьшее число полуплоскостей для всех книжных вложений графа. Книжное вложение используется для некоторых других инвариантов графа, включая ширину страницы и книжное число скрещиваний. Открытыми проблемами, касающимися книжного вложения, являются
rdf:langString
Книжкове вкладення в теорії графів — узагальнення планарного вкладення графа до вкладення в книжку — набір напівплощин, які мають межею одну й ту саму пряму. Зазвичай потрібно, щоб вершини графа лежали на цій межі, а ребра мають міститися всередині однієї сторінки. Книжкова товщина (або кількість сторінок) графа — найменша кількість напівплощин серед усіх книжкових вкладень графа. Книжкове вкладення використовують для деяких інших інваріантів графа, серед яких ширина сторінки та книжкове число схрещень. Відкритими проблемами, що стосуються книжкового вкладення, є
rdf:langString
rdf:langString
Book embedding
rdf:langString
Embebido en libro
rdf:langString
Книжное вложение
rdf:langString
Книжкове вкладення
xsd:integer
3987703
xsd:integer
1058071683
rdf:langString
Donald Knuth
rdf:langString
Donald
rdf:langString
Knuth
xsd:integer
1968
rdf:langString
In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings into a book, a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, called the spine, and the edges are required to stay within a single half-plane. The book thickness of a graph is the smallest possible number of half-planes for any book embedding of the graph. Book thickness is also called pagenumber, stacknumber or fixed outerthickness. Book embeddings have also been used to define several other graph invariants including the pagewidth and book crossing number. Every graph with n vertices has book thickness at most , and this formula gives the exact book thickness for complete graphs. The graphs with book thickness one are the outerplanar graphs. The graphs with book thickness at most two are the subhamiltonian graphs, which are always planar; more generally, every planar graph has book thickness at most four. All minor-closed graph families, and in particular the graphs with bounded treewidth or bounded genus, also have bounded book thickness. It is NP-hard to determine the exact book thickness of a given graph, with or without knowing a fixed vertex ordering along the spine of the book. Testing the existence of a three-page book embedding of a graph, given a fixed ordering of the vertices along the spine of the embedding, has unknown computational complexity: it is neither known to be solvable in polynomial time nor known to be NP-hard. One of the original motivations for studying book embeddings involved applications in VLSI design, in which the vertices of a book embedding represent components of a circuit and the wires represent connections between them. Book embedding also has applications in graph drawing, where two of the standard visualization styles for graphs, arc diagrams and circular layouts, can be constructed using book embeddings. In transportation planning, the different sources and destinations of foot and vehicle traffic that meet and interact at a traffic light can be modeled mathematically as the vertices of a graph, with edges connecting different source-destination pairs. A book embedding of this graph can be used to design a schedule that lets all the traffic move across the intersection with as few signal phases as possible. In bioinformatics problems involving the folding structure of RNA, single-page book embeddings represent classical forms of nucleic acid secondary structure, and two-page book embeddings represent pseudoknots. Other applications of book embeddings include abstract algebra and knot theory.
rdf:langString
En teoría de grafos, un embebido en libro es una generalización del embebido plano de un grafo a embebidos en un libro, una colección de semiespacios, todos con la misma recta como límite. Por lo general, se requiere que los vértices del grafo se encuentren en esta línea límite, llamada "columna vertebral", y se requiere que los vínculos permanezcan dentro de un solo semiplano. El espesor del libro de un grafo es el número más pequeño posible de semiplanos para cualquier embebido en libro del grafo. El grosor del libro también se denomina número de páginas, número de pila o grosor exterior fijo. Los embebidos en libro también se han utilizado para definir varios otros , incluido el ancho de página y el número de cruces del libro. Cada grafo con n vértices tiene un grosor de libro como máximo de , y esta fórmula proporciona el grosor del libro exacto para un grafo completo. Los grafos con grosor de libro uno son los grafos planos exteriores. Los grafos con grosor de libro como máximo dos se denominan , que siempre son planos; de manera más general, cada grafo plano tiene un grosor de libro de cuatro como máximo. Todos los , y en particular los grafos con acotado o genus acotado, también tienen grosor de libro acotado. Determinar el grosor exacto del libro de un grafo dado, con o sin conocer un orden de vértices fijo en el lomo del libro, es un problema de complejidad NP-hard. Probar la existencia de un libro de tres páginas embebido de un grafo, dado un orden fijo de los vértices en el lomo del libro, tiene una complejidad computacional desconocida: no se sabe que sea resoluble en tiempo polinomial ni que sea de dificultad NP. Una de las motivaciones originales para estudiar embebidos en libros involucró aplicaciones en el diseño de integración a muy gran escala, proceso en el que los vértices de un embebido en libro representan componentes de un circuito y los cables representan las conexiones entre ellos. Los embebidos en libros también tiene aplicaciones en dibujo de grafos, donde dos de los estilos de visualización estándar para grafos, los y el , pueden construirse mediante embebidos en libros. En planificación de transporte, las diferentes fuentes y destinos del tráfico peatonal y vehicular que se encuentran e interactúan en un semáforo se pueden modelar matemáticamente como los vértices de un grafo, con vínculos que conectan diferentes pares de origen y destino. Se puede usar un embebido en libro de este grafo para diseñar un cronograma que permita que todo el tráfico se mueva a través de la intersección con la menor cantidad posible de fases de semáforo. En los problemas de bioinformática que involucran la estructura de plegado del ácido ribonucleico, los embebidos en libro de una sola página representan formas clásicas de la , y los embebidos en libro de dos páginas representan pseudonudos. Otras aplicaciones de embebidos en libro incluyen el álgebra abstracta y la teoría de nudos.
rdf:langString
Книжное вложение в теории графов — обобщение планарного вложения графа до вложения в книгу — набор полуплоскостей, имеющих одну и ту же прямую в качестве границы. Обычно требуется, чтобы вершины графа лежали на этой границе, а рёбра должны находиться внутри одной страницы. Книжная толщина (или число страниц) графа — наименьшее число полуплоскостей для всех книжных вложений графа. Книжное вложение используется для некоторых других инвариантов графа, включая ширину страницы и книжное число скрещиваний. Любой граф с n вершинами имеет книжную толщину максимум . Эта граница близка для полных графов. Однако подразделение каждого ребра может сократить книжную толщину к величине, пропорциональной корню квадратному из n. Графы с книжной толщиной один являются внешнепланарными графами, а графы с книжной толщиной не более двух являются подгамильтоновыми, которые всегда планарны. Любой планарный граф имеет книжную толщину, не превышающую четырёх. Все минорно замкнутые семейства графов, и, в частности, графы с ограниченной древесной шириной или ограниченным родом, также имеют ограниченную книжную толщину. Определение точной книжной толщины заданного графа является NP-трудной задачи, независимо от того, известен или нет порядок вершин на корешке. Одной из начальных поводов для изучения книжного вложения было применение его в разработке СБИС, где вершины книжного вложения представляют компоненты, а рёбра представляют соединения между компонентами.При визуализации графов два стандартных стиля представления графов, дуговые диаграммы и круговые расположения, можно построить с помощью книжного вложения.Различные начальные и конечные точки движения пешеходов и машин, которые регулируются светофором, могут быть смоделированы математически как вершины графа, а рёбра будут представлять пары начало-конец, книжное же вложение этого графа можно использовать для создания режима работы светофора, чтобы обеспечить регулировку движения с минимальным числом состояний светофора.В задачах биоинформатики, работающих со структурами РНК, одностраничное книжное вложение представляет классическую форму , а двухстраничное вложение представляет псевдоузлы.Книжное вложение используется также в общей алгебре и теории узлов. Открытыми проблемами, касающимися книжного вложения, являются
* Ограничена ли книжная толщина произвольного графа функцией его подразбиений
* Достаточно ли знать порядок вершин на корешке, чтобы проверить, что граф имеет трёхстраничное вложение
* Существует ли планарный граф, книжная толщина которого равна четырём
* Сколько пересечений на корешке необходимо для трёхстраничного топологического вложения (в этом случае рёбра могут переходить со страницы на страницу через корешок) произвольного графа.
rdf:langString
Книжкове вкладення в теорії графів — узагальнення планарного вкладення графа до вкладення в книжку — набір напівплощин, які мають межею одну й ту саму пряму. Зазвичай потрібно, щоб вершини графа лежали на цій межі, а ребра мають міститися всередині однієї сторінки. Книжкова товщина (або кількість сторінок) графа — найменша кількість напівплощин серед усіх книжкових вкладень графа. Книжкове вкладення використовують для деяких інших інваріантів графа, серед яких ширина сторінки та книжкове число схрещень. Будь-який граф з вершинами має книжкову товщину не більше . Ця межа близька до повних графів. Однак поділ кожного ребра може зменшти книжкову товщину до величини, пропорційної кореню квадратному з . Графи з книжковою товщиною один є зовніпланарними графами, а графи з книжковою товщиною не більше двох є підгамільтоновими, які завжди планарні. Будь-який планарний граф має книжкову товщину, що не перевищує чотирьох. Всі мінорно замкнуті сімейства графів, і, зокрема, графи з обмеженою деревною шириною або обмеженим родом, також мають обмежену книжкову товщину. Визначення точної книжкової товщини заданого графа є NP-складною задачею, незалежно від того, чи відомий порядок вершин на корінці. Одним із початкових приводів вивчення книжкового вкладення було його застосування в розробці НВІС, де вершини книжкового вкладення представляють компоненти, а ребра — з'єднання між ними. При візуалізації графів за допомогою книжкового вкладення можна побудувати два стандартні стилі подання графів: дугові діаграми та колові розташування ,. Різні початкові та кінцеві точки руху пішоходів і машин, що регульованого світлофором, можна математично змоделювати як вершини графа, а ребра будуть представляти пари початок-кінець, книжкове ж вкладення цього графа можна використати для розробки режиму роботи світлофора, щоб забезпечити регулювання руху з найменшим числом станів світлофора. У задачах біоінформатики, що працюють зі структурами РНК, односторінкове книжкове вкладення представляє класичну форму , а двосторінкове вкладення представляє псевдовузли. Книжкове вкладення використовують також у загальній алгебрі та теорії вузлів. Відкритими проблемами, що стосуються книжкового вкладення, є
* Чи обмежена книжкова товщина довільного графа функцією його підрозбиттів?
* Чи достатньо знати порядок вершин на корінці, щоб перевірити, чи граф має тристорінкове вкладення?
* Чи існує планарний граф, книжкова товщина якого дорівнює чотирьом?
* Скільки перетинів на корінці необхідно для тристорінкового топологічного вкладення (у цьому випадку ребра можуть переходити зі сторінки на сторінку через корінець) довільного графа?
xsd:nonNegativeInteger
67485
