Ir al contenido

Diferencia entre revisiones de «Embebido en libro»

De Wikipedia, la enciclopedia libre
Explorar historial interactivamente
← Ir a diferencia anteriorIr a siguiente diferencia →
Contenido eliminado Contenido añadido
VisualWikitexto
Línea 396: Línea 396:
}}.</ref>
}}.</ref>


Debido a que los grafos de grosor de libro dos son grafos planos, obedecen al [[ planar separator theorem]]: tienen separadores, subconjuntos de vértices cuya eliminación divide el grafo en partes con un máximo de vértices {{math|2''n''/3}} cada una, con solo vértices <math>O(\sqrt n)</math> en el separador. Aquí, {{mvar|n}} se refiere al número de vértices en el grafo. Sin embargo, existen grafos de grosor de libro tres que no tienen separadores de tamaño sublineal.<ref name="dsw15">{{citation|title=3-Monotone Expanders|first1=Vida|last1=Dujmović|author1-link=Vida Dujmović|first2=Anastasios|last2=Sidiropoulos|first3=David R.|last3=Wood|author3-link=David Wood (mathematician)|arxiv=1501.05020|year=2015|bibcode=2015arXiv150105020D}}, improving an earlier result showing the existence of expanders with constant pagenumber from {{citation
Debido a que los grafos de grosor de libro dos son grafos planos, obedecen al [[teorema del separador de planos]]: tienen separadores, subconjuntos de vértices cuya eliminación divide el grafo en partes con un máximo de {{math|2''n''/3}} vértices cada una, con solo <math>O(\sqrt n)</math> vértices en el separador. Aquí, {{mvar|n}} se refiere al número de vértices en el grafo. Sin embargo, existen grafos de grosor de libro tres que no tienen separadores de tamaño sublineal.<ref name="dsw15">{{citation|title=3-Monotone Expanders|first1=Vida|last1=Dujmović|author1-link=Vida Dujmović|first2=Anastasios|last2=Sidiropoulos|first3=David R.|last3=Wood|author3-link=David Wood (matemático)|arxiv=1501.05020|year=2015|bibcode=2015arXiv150105020D}}, mejorando un resultado anterior que mostraba la existencia de expansores con número de página constante de {{citation
|last= Bourgain|first= Jean|author-link= Jean Bourgain
|last= Bourgain|first= Jean|author-link= Jean Bourgain
|doi= 10.1016/j.crma.2009.02.009
|doi= 10.1016/j.crma.2009.02.009

Revisión del 09:12 3 sep 2022

Uno o varios wikipedistas están trabajando actualmente en este artículo o sección. Puede tener lagunas de contenido o deficiencias de formato.
Si quieres, puedes ayudar y editar, pero antes de realizar correcciones mayores contáctalos en sus páginas de discusión o en la del artículo para poder coordinar la redacción. La finalidad de este mensaje es reducir los conflictos de edición. Si el trabajo de edición se concentra en una sección coloca allí la plantilla para permitir a otros editar la página.
Uso de esta plantilla: {{En desarrollo|nombre de usuario|t={{sust:CURRENTTIMESTAMP}}}} o {{sust:En desarrollo}}
Un libro de tres páginas embebido del grafo completo K5. Debido a que no es un grafo plano, no es posible embeber este grafo sin cruces en menos páginas, por lo que el grosor del libro es tres

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 invariantes de grafo, 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 grafos subhamiltonianos, que siempre son planos; de manera más general, cada grafo plano tiene un grosor de libro de cuatro como máximo. Todos los familias de grafos cerrados menores, y en particular los grafos con ancho de árbol 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 diagramas de arcos y el diseño circular, 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 estructura secundaria de un ácido nucleico, 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.

Historia

La noción de libro, como espacio topológico, fue definida por C. A. Persinger y Gail Atneosen en la década de 1960.[1]​[2]​ Como parte de este trabajo, Atneosen ya consideró embebidos de grafos en libros. Los embebidos que estudió usaban la misma definición que los embebidos de grafos en cualquier otro espacio topológico: los vértices están representados por puntos distintos, los vínculos están representados por curvas y la única forma en que dos vínculos pueden intersecarse es que se encuentren en un punto final común.

A principios de la década de 1970, Paul C. Kainen y L. Taylor Ollmann desarrollaron un tipo de embebido más restringido que se utilizó en la mayoría de las investigaciones posteriores. En su formulación, los vértices del grafo deben colocarse en el lomo del libro, y cada vínculo debe estar en una sola página.[3]​[4]​

Los hitos importantes en el desarrollo posterior de los embebidos en libro incluyen la prueba de Mihalis Yannakakis a finales de la década de 1980 de que un grafo plano tiene un grosor de libro de cuatro como máximo,[5]​[6]​ y el descubrimiento a finales de la década de 1990 de conexiones cercanas entre los embebidos en libro y la bioinformática.[7]​

Definiciones

El grafo del problema de los tres servicios K3,3 no se puede embeber en un libro de 2 páginas, pero se puede dibujar como se muestra en un libro de 2 páginas con un solo cruce. Por lo tanto, su número de cruce de libros de 2 páginas es 1
Este embebido de 1 página del grafo diamante tiene un ancho de página de 3, porque el rayo amarillo cruza tres vínculos

Un libro es un tipo particular de espacio topológico, también llamado fan de semiplanos.[1]​[8]​ Consiste en una sola recta ℓ, denominada lomo o contraportada del libro, junto con una colección de uno o más semiespacios, denominados páginas u hojas del libro,[9]​ teniendo cada una el lomo como límite. Los libros con un número finito de páginas pueden ser embebidos en un espacio tridimensional, por ejemplo, eligiendo ℓ para que sea el eje z de un sistema tridimensional de coordenadas cartesianas y eligiendo las páginas para que sean los semiplanos k cuyo ángulo diedro con respecto al plano xz es un múltiplo entero de 2Π/k.[10]​

Un dibujo de libro de un grafo finito G sobre un libro B es un dibujo de G sobre B tal que cada vértice de G se representa como un punto en el lomo de B, y cada vínculo de G se dibuja como un curva que se encuentra dentro de una sola página de B. El número de cruce del libro de la página k de G es el número de cruces mínimo en un dibujo del libro de k páginas.[11]​

Un embebido en libro de G en B es un dibujo de libro que forma un grafo embebido de G en B. Es decir, es un dibujo de libro de G en B que no carece de cruces entre vínculos.

Cada grafo finito tiene un libro embebido con un número suficientemente grande de páginas. Por ejemplo, siempre es posible incrustar cada vínculo del grafo en su propia página separada.

El grosor del libro, el número de páginas o el número de pila de G es el número mínimo de páginas requeridas para el embebido de  G en un libro.

Otro parámetro que mide la calidad del embebido de un libro, más allá de su número de páginas, es su ancho de página. Este es el número máximo de vínculos que puede cruzar un rayo cualquiera perpendicular al lomo dentro de una sola página. De manera equivalente (para embebidos en libro en los que cada vínculo se dibuja como una curva monótona), es el tamaño máximo de un subconjunto de vínculos dentro de una sola página de modo que los intervalos definidos en el lomo por pares de puntos finales de los vínculos que se cruzan entre sí.[12]​[13]​[14]​

Es crucial para estas definiciones que los vínculos deben permanecer dentro de una sola página del libro. Como ya observó Atneosen, si los vínculos pueden pasar de una página a otra en el lomo del libro, entonces cada grafo puede estar embebido en un libro de tres páginas.[15]​[2]​[16]​ Para una embebido de libro topológico de tres páginas en el que se permiten cruces en el lomo, cada grafo puede incrustarse con un número logarítmico como máximo de cruces en el lomo por vínculo,[15]​ y algunos grafos necesitan estos cruces de vínculos en el lomo.[17]​

Grafos específicos

Como se muestra en la primera figura, el grosor del libro del grafo completo K5 es tres: como grafo no plano, su grosor del libro es mayor que dos, pero existe un libro embebido con tres páginas. Más generalmente, el grosor del libro de cada grafo completo con n ≥ 4 vértices es exactamente . Este resultado también proporciona una cota superior sobre el máximo grosor de libro posible de cualquier grafo de n vértices.[10]​

El número de cruce de dos páginas del grafo completo Kn es

haciendo valer una conjetura aún no probada de Anthony Hill sobre cuál debería ser el número de cruce sin restricciones de este grafo. Es decir, si la conjetura de Hill es correcta, entonces el dibujo de este grafo que minimiza el número de cruces es un dibujo de dos páginas.[18]​

El grosor del libro del grafo bipartito completo Ka,b es como máximo min(a,b). Para construir un dibujo con este grosor de libro, para cada vértice en el lado más pequeño de la bipartición, se pueden colocar los vínculos incidentes con ese vértice en su propia página. Este límite no siempre es estrecho; por ejemplo, K4,4 tiene un grosor de libro de tres, no de cuatro. Sin embargo, cuando los dos lados del grafo están muy desequilibrados, con b > a(a − 1), el grosor del libro de Ka,b es exactamente a.[10]​[19]​

Para el grafo de Turán T(kr,r) (un grafo multipartito completo Kk,k,... formado por r conjuntos independientes de k vértices por conjunto independiente, con una arista entre cada dos vértices de diferentes conjuntos independientes), el grosor del libro t se intercala entre

y cuando r es impar, el límite superior se puede mejorar hasta

[10]​[20]​

El grosor de un embebido en libro de grafos binarios como el grafo de De Bruijn, los grafos de intercambio aleatorio y los ciclos conectados al cubo (cuando son lo suficientemente grandes para no ser planos), es exactamente tres.[21]​

Propiedades

Planaridad y planaridad exterior

El grafo de Goldner-Harary, un grafo plano con espesor de libro 3

El grosor del libro de un grafo G dado es como máximo uno si y solo si G es un grafo plano exterior, caracterizado por tener un embebido plano en el que todos los vértices pertenecen a la cara exterior del embebido. Para un grafo de este tipo, colocar los vértices en el mismo orden en el lomo en el que aparecen en la cara exterior proporciona un embebido de libro de una página del grafo dado (un punto de articulación del grafo aparecerá necesariamente más de una vez en el orden cíclico de los vértices alrededor de la cara exterior, pero solo una de esas copias debe incluirse en el embebido en el libro). Por el contrario, el embebido en un libro de una página es automáticamente un plano exterior, porque si un grafo está embebido en una sola página, y otro semi plano se adjunta al lomo para extender su página a un plano completo, entonces la cara exterior del embebido incluye todo el medio plano agregado, y todos los vértices se encuentran en esta cara exterior.[10]​[12]​

Cada embebido de un libro de dos páginas es un caso especial de embebido plano, porque la unión de dos páginas de un libro es un espacio topológicamente equivalente a todo el plano. Por lo tanto, cada grafo con grosor de libro dos es automáticamente un grafo plano. Más precisamente, el grosor del libro de un grafo G es como máximo dos si y solo si G es un subgrafo de un grafo plano que tiene un camino hamiltoniano.[10]​ Si a un grafo se le da un embebido de dos páginas, se puede aumentar a un grafo hamiltoniano plano agregando (en cualquier página) vínculos adicionales entre dos vértices consecutivos en el lomo que aún no son adyacentes, y entre el primero y el último vértices del lomo. El grafo de Goldner-Harary proporciona un ejemplo de un grafo plano que no tiene un grosor de libro dos: es un grafo plano, por lo que no es posible agregarle ningún vínculo mientras se conserva la planaridad, y no tiene un ciclo hamiltoniano.[10]​ Debido a esta caracterización por ciclos hamiltonianos, los grafos que tienen embebidos en libro de dos páginas también se conocen como grafos subhamiltonianos.[12]​

Todos los grafos planos cuyo grado máximo es a lo sumo cuatro tienen un grosor de libro como máximo de dos.[22]​ Los 3-árboles planos tienen un grosor de libro de tres como máximo.[23]​ De manera más general, todos los grafos planos tienen un grosor de libro de cuatro.[5]​[6]​[24]​ Mihalis Yannakakis afirmó en 1986[6]​ que existen algunos grafos planos que tienen un grosor de libro exactamente cuatro. Sin embargo, no se conoció una prueba detallada de esta afirmación hasta 2020, cuando fue presentada en un artículo de revista posterior,[5]​ por Bekos et al.[24]​ que presentaron grafos planos con ancho de árbol 4 que requieren cuatro páginas en cualquier libro embebido.

Comportamiento bajo subdivisiones

El grosor del libro del grafo de diamante aumenta después de dividir sus vínculos

Subdividir cada vínculo de un grafo en rutas de dos vínculos, al agregar nuevos vértices dentro de cada vínculo, a veces puede aumentar el grosor del libro. Por ejemplo, el grafo diamante tiene un grosor de libro 1 (es plano exterior), pero su subdivisión tiene un grosor de libro 2 (es plano y subhamiltoniano pero no plano exterior). Sin embargo, este proceso de subdivisión a veces también puede reducir significativamente el grosor del libro del grafo subdividido. Por ejemplo, el grosor del libro de un grafo completo Kn es proporcional a su número de vértices, pero al subdividir cada una de sus aristas en un camino de dos vínculos se produce una subdivisión cuyo grosor del libro es mucho menor, solo .[25]​ A pesar de la existencia de ejemplos como este, Blankenship y Oporowski (1999) se ha conjeturado que el grosor del libro de una subdivisión no puede ser mucho más pequeño que el del grafo original. Específicamente, se propuso que existe una función f tal que, para cada grafo G y para el grafo H formado reemplazando cada vínculo en G por un camino de dos vínculos, que si el grosor del libro de H es t entonces el grosor del libro de G es como máximo f(t).[16]​ Su conjetura resultó ser falsa: los grafos formados por productos cartesianos en estrellas y teselados triangulares tienen un grosor de libro ilimitado, pero subdividir sus vínculos en caminos de seis vínculos reduce su grosor de libro a tres.[26]​

Relación con otros invariantes de grafos

El grosor de un libro de embebido está relacionado con el grosor del grafo, el número de grafos planos necesarios para cubrir los vínculos de un grafo dado. Un grafo G tiene grosor θ si se puede dibujar en el plano, y sus vínculos ser coloreados con θ colores distintos, de tal forma que no se cruzan entre sí vínculos del mismo color. Análogamente, un grafo G tiene grosor de libro θ si se puede dibujar en un semiespacio, con sus vértices en el límite del semiplano, y con sus vínculos coloreados con θ colores sin cruce entre dos vínculos del mismo color. En esta formulación del grosor de un libro, los colores de los vínculos corresponden a las páginas del libro embebido. Sin embargo, el espesor y el grosor del libro pueden ser muy diferentes entre sí: existen grafos (subdivisiones de grafos completos) que tienen un grosor de libro ilimitado,[25]​[15]​[16]​ a pesar de tener un espesor dos.[25]​

Los grafos de ancho de árbol k tienen un grosor de libro como máximo de k + 1[27]​[28]​ y este límite es estrecho para k > 2.[27]​ Los grafos con m vínculos tienen un grosor de libro de ,[29]​ y los grafos de genus g tienen un grosor de libro de .[30]​ Más generalmente, cada familia de grafos cerrados menores tiene un grosor de libro acotado.[31]​[32]​ Por otro lado, los grafos 1-planos, que no están cerrados bajo menores,[31]​ también tienen un grosor de libro acotado,[33]​ pero algunos grafos 1-planos, incluido K2,2,2,2, tienen un grosor de libro de al menos cuatro.[34]​

Cada menor superficial de un grafo de espesor de libro acotado es un grafo disperso, cuya relación entre vínculos y vértices está acotada por una constante que depende únicamente de la profundidad del menor y del espesor del libro. Es decir, en la terminología de Nešetřil y Ossona de Mendez (2012), los grafos de espesor de libro acotado poseen expansión limitada.[31]​ Sin embargo, incluso los grafos de grado acotado, un requisito mucho más estricto que poseer una expansión acotada, pueden tener un espesor de libro ilimitado.[35]​

Debido a que los grafos de grosor de libro dos son grafos planos, obedecen al teorema del separador de planos: tienen separadores, subconjuntos de vértices cuya eliminación divide el grafo en partes con un máximo de 2n/3 vértices cada una, con solo vértices en el separador. Aquí, n se refiere al número de vértices en el grafo. Sin embargo, existen grafos de grosor de libro tres que no tienen separadores de tamaño sublineal.[36]​

Los vínculos dentro de una sola página de un libro embebido se comportan de alguna manera como un la estructura de una pila de datos. Esto se puede formalizar considerando una secuencia arbitraria de operaciones empujar y eliminar elementos en una pila, y formando un grafo en el que las operaciones de la pila corresponden a los vértices del grafo, colocados en orden secuencial en el lomo de un libro embebido. Entonces, si se dibuja un vínculo de cada operación emergente que extrae un objeto x de la pila, a la operación de inserción anterior que empujó x, el grafo resultante automáticamente tendrá un embebido de una página. Por esta razón, el número de páginas de un grafo también se ha denominado número de pila. De la misma manera, se puede considerar una secuencia arbitraria de operaciones de entrada y salida de una cola de datos, y formar un grafo que tenga estas operaciones como sus vértices, colocados en orden en el lomo de una sola página, con un vínculo entre cada operación de puesta en cola y la correspondiente puesta en cola. Luego, en este grafo, cada dos vínculos se cruzarán o cubrirán intervalos inconexos en el lomo. Por analogía, los investigadores han definido un embebido en cola de un grafo como una embebido en un libro topológico, de modo que cada vértice se encuentra en el lomo, cada vínculo se encuentra en una sola página y cada dos vínculos en la misma página se cruzan o cubren intervalos disjuntos en el lomo. El número mínimo de páginas necesarias para el embebido en cola de un grafo se denomina número de cola.[31]​[37]​[38]​

Complejidad computacional

Un grafo circular, el grafo de intersección de las cuerdas tendidas en un círculo. Para embebidos en libro con un orden de vértices fijo, encontrar el grosor del libro es equivalente a colorear un grafo circular derivado

Encontrar el grosor del libro de un grafo es NP-hard. Esto se deriva del hecho de que encontrar ciclos hamiltonianos en grafos planares máximos es NP-completo. En un grafo plano máximo, el grosor del libro es dos si y solo si existe un ciclo hamiltoniano. Por lo tanto, también es NP-completo probar si el grosor del libro de un grafo plano máximo dado es dos.[39]​

Si se fija un orden de los vértices de un grafo en el lomo de una embebido, entonces se puede encontrar una embebido de dos páginas (si existe) en complejidad temporal, como una instancia de planarity testing para un grafo formado al aumentar el grafo dado con un ciclo que conecta los vértices en el orden de su columna vertebral.[7]​ Unger (1992) afirmó que la búsqueda de embebidos de tres páginas con un orden de lomo fijo también se puede realizar en complejidad temporal, aunque su descripción de este resultado omite muchos detalles.[40]​ Sin embargo, para grafos que requieren cuatro o más páginas, el problema de encontrar una embebido con el mínimo número posible de páginas sigue siendo NP-difícil, a través de una equivalencia al problema NP-difícil de coloring circle graphs, los grafo de interseccións de chords de un círculo . Dado un grafo G con una columna vertebral fija que ordena sus vértices, dibujar estos vértices en el mismo orden alrededor de un círculo y dibujar los vínculos de G como segmentos de línea produce una colección de cuerdas que representan G. Entonces se puede formar un grafo circular que tenga las cuerdas de este diagrama como vértices y pares de cuerdas cruzadas como aristas. Un coloreado del grafo circular representa una partición de los vínculos de G en subconjuntos que se pueden dibujar sin cruzarse en una sola página. Por lo tanto, una coloración óptima es equivalente a una embebido óptima de libros. Dado que la coloración de grafos circulares con cuatro o más colores es NP-difícil, y dado que cualquier grafo circular puede formarse de esta manera a partir de algún problema de embebido de libros, se deduce que el embebido óptima de libros también es NP-difícil.[41]​[42]​[43]​ Para un orden de vértices fijo en el lomo de un dibujo de un libro de dos páginas, también es NP-difícil minimizar el número de cruces cuando este número es distinto de cero.[42]​

Si se desconoce el orden del lomo pero se proporciona una partición de los vínculos en dos páginas, entonces es posible encontrar una embebido de 2 páginas (si existe) en complejidad temporal mediante un algoritmo basado en SPQR tree.[44]​[45]​ Sin embargo, es NP-completo encontrar una embebido de 2 páginas cuando no se conoce el orden del lomo ni la partición del vínculo. Encontrar el número de cruce de libro de un grafo también es NP-difícil, debido a la NP-completitud del caso especial de probar si el número de cruce de 2 páginas es cero.

Como consecuencia de la expansión acotada, el problema problema de isomorfismo de subgrafos, de encontrar si un grafo de patrón de tamaño acotado existe como un subgrafo de un grafo más grande, se puede resolver en tiempo lineal cuando el grafo más grande tiene un grosor de libro acotado. Lo mismo es cierto para detectar si el grafo de patrón es un subgrafo inducido del grafo más grande o si tiene un homomorfismo de grafos del grafo más grande.[46]​[47]​ Por la misma razón, el problema de probar si un grafo de grosor de libro acotado obedece a una fórmula dada de lógica de primer orden es fixed-parameter tractable.[48]​

Bekos, Kaufmann y Zielke (2015) describe un sistema para encontrar embebidos en libro óptimas transformando el problema en una instancia de Problema de satisfacibilidad booleana y aplicando un solucionador SAT al problema resultante. Afirman que su sistema es capaz de encontrar una embebido óptima para grafo plano de 400 vértices en aproximadamente 20 minutos.[34]​

Aplicaciones

Multiprocesamiento tolerante a fallas

Una de las principales motivaciones para estudiar el embebido de libros citada por Chung, Leighton y Rosenberg (1987) implica una aplicación en el diseño de Integración a muy gran escala, para la organización de fault-tolerant multiprocesamientos. En el sistema DIOGENES desarrollado por estos autores, los Unidad central de procesamiento de un sistema multiprocesador se organizan en una secuencia lógica correspondiente al lomo de un libro (aunque esta secuencia no necesariamente se coloca en una línea en el physical layout de este sistema). Los enlaces de comunicación que conectan estos procesadores se agrupan en "paquetes" que corresponden a las páginas de un libro y actúan como stacks: conectar uno de los procesadores al comienzo de un nuevo enlace de comunicaciones empuja todos los enlaces anteriores hacia arriba en el paquete y conectar otro El procesador al final de un enlace de comunicación lo conecta con el que está en la parte inferior del paquete y baja todos los demás. Debido a este comportamiento de pila, un solo paquete puede manejar un conjunto de enlaces de comunicaciones que forman los vínculos de una sola página en un libro embebido. Al organizar el enlaces de esta manera, se puede implementar una amplia variedad de diferentes topologías de red, independientemente de qué procesadores hayan fallado, siempre que queden suficientes procesadores sin fallas para implementar la red. Las topologías de red que puede implementar este sistema son exactamente aquellas que tienen un grosor de libro como máximo igual al número de paquetes que se han puesto a disposición.[39]​ el embebido de libros también se puede usar para modelar la ubicación de los cables que conectan los componentes VLSI en las capas de un circuito.[49]​

Clasificación de pilas

Otra aplicación citada por Chung, Leighton y Rosenberg (1987) se refiere a la clasificación de permutación utilizando stack. Un resultado influyente de txt, mostró que un sistema que procesa un data stream empujando elementos entrantes a un y luego, en los momentos elegidos apropiadamente, sacarlos de la pila a un flujo de salida puede sort los datos si y solo si su orden inicial es descrito por un permutación que evita el permutation pattern 231.[50]​ Desde entonces, se ha trabajado mucho en problemas similares de clasificación de flujos de datos por sistemas más generales de pilas y colas. En el sistema considerado por Chung, Leighton y Rosenberg (1987), cada elemento de un flujo de datos de entrada debe colocarse en una de varias pilas. Luego, una vez que todos los datos se han enviado de esta manera, los elementos se extraen de estas pilas (en el orden apropiado) en un flujo de salida. Como Chung et al. observe, una permutación dada puede ser ordenada por este sistema si y solo si un cierto grafo, derivado de la permutación, tiene un libro embebido con los vértices en un cierto orden fijo en el lomo y con un número de páginas que es como máximo igual al número de pilas.[39]​

Control de tráfico

Una intersección de tráfico. Los cuatro pares entrantes y cuatro salientes de carriles directos, los dos carriles intermedios de giro y las cuatro esquinas de los cruces de peatones se pueden representar como un conjunto de 14 vértices en el lomo de un libro de embebido, con vínculos que representan recorridos entre estos puntos

Como se describe en Kainen (1990), se puede usar un libro embebido para describir las fases de un semáforo en una intersección controlada. En una intersección, los carriles de tráfico de entrada y salida (incluidos los extremos de los cruces peatonales y los carriles para bicicletas, así como los carriles para vehículos motorizados) pueden representarse como los vértices de un grafo, colocados en el lomo de un libro embebidos en sentido horario. orden alrededor del cruce. Los caminos a través de la intersección tomados por el tráfico para pasar de un carril de entrada a un carril de salida pueden representarse como los vínculos de un grafo no dirigido. Por ejemplo, este grafo podría tener un vínculo desde un carril de tráfico de entrada a uno de salida que pertenecen al mismo segmento de la carretera, lo que representa un giro en U desde ese segmento de regreso a ese segmento, solo si los giros en U están permitidos en el unión. Para un subconjunto dado de estos vínculos, el subconjunto representa una colección de caminos que se pueden recorrer sin interferencia entre sí si y solo si el subconjunto no incluye ningún par de vínculos que se cruzarían si los dos vínculos se colocaran en una sola. página de un libro embebido. Por lo tanto, el embebido de un libro de este grafo describe una partición de las rutas en subconjuntos que no interfieren, y el grosor del libro de este grafo (con su embebido fija en el lomo) proporciona el número mínimo de fases distintas necesarias para un programa de señalización que incluye todas las rutas de tráfico posibles a través del cruce.[51]​

Dibujo grafo

Un diagrama de arcos del grafo de Goldner-Harary. Para crear un diagrama plano, dos triángulos del grafo se han subdividido en cuatro por la línea roja discontinua, lo que hace que uno de los vínculos del grafo se extienda tanto por encima como por debajo de la línea

el embebido de libros también se ha aplicado con frecuencia en la visualización de datos de red. Dos de los diseños estándar en dibujo de grafos, diagramas de arco[52]​ y diseños circulares,[53]​ se pueden ver como embebidos en libro, y el embebido de libros también se ha aplicado en la construcción de diseños agrupados,[44]​ embebidos simultáneas,[54]​ y dibujos de grafos tridimensionales.[55]​

Un arc diagram[52]​ o embebido lineal[42]​ coloca los vértices de un grafo en una línea y dibuja los vínculos del grafo como semicírculos por encima o por debajo de esta línea, lo que a veces también permite dibujar vínculos en segmentos de la línea. Este estilo de dibujo corresponde a un libro embebido con una página (si todos los semicírculos están sobre la línea) o dos páginas (si se usan ambos lados de la línea), y se introdujo originalmente como una forma de estudiar el crossing numbers de los grafos.[56]​[57]​ Los grafos planos que no tienen embebidos en libro de dos páginas también se pueden dibujar de manera similar, al permitir que sus vínculos se representen mediante varios semicírculos por encima y por debajo de la línea. Tal dibujo no es una embebido de libro según la definición habitual, pero se ha denominado embebido de libro topológica.[58]​ Para cada grafo plano, siempre es posible encontrar una embebido en la que cada vínculo cruce la columna como máximo una vez.[59]​

Diseño circular del grafo de Chvátal

En otro estilo de dibujo, el circular layout, los vértices de un grafo se colocan en un círculo y los vínculos se dibujan dentro o fuera del círculo.[53]​ Una vez más, la ubicación de los vínculos dentro del círculo (por ejemplo, como segmentos de línea recta) corresponde al dibujo de un libro de una página, mientras que la ubicación tanto dentro como fuera del círculo corresponde al dibujo de un libro de dos páginas.[60]​

Para los dibujos de una página de cualquier estilo, es importante mantener un número pequeño de cruces como una forma de reducir el desorden visual del dibujo. Minimizar el número de cruces es NP-completo,[42]​ pero puede aproximarse con


h una relación de aproximación de O(log2 n) donde n es el número de vértices.[61]​ Minimizar el número de cruce de una o dos páginas es complejidad parametrizada cuando se parametriza mediante el cyclomatic number del grafo dado, o mediante una combinación del número de cruce y el treewidth del grafo.[62]​[63]​ También se han ideado métodos heurísticos para reducir la complejidad del cruce, basados, p. en un orden de inserción de vértice cuidadoso y en local optimization.[53]​

los embebidos en libro de dos páginas con una partición fija de los vínculos en páginas pueden interpretarse como una forma de clustered planarity, en la que el grafo dado debe dibujarse de tal manera que partes del grafo (los dos subconjuntos de vínculos) se colocan en el dibujo de una manera que refleje su agrupación.[44]​ el embebido de libros de dos páginas también se ha utilizado para encontrar simultaneous embedding de grafos, en los que se dan dos grafos en el mismo conjunto de vértices y se debe encontrar una ubicación para los vértices en la que ambos grafos se dibujen planamente con vínculos rectos.[54]​

También se han utilizado embebidos en libro con más de dos páginas para construir dibujos tridimensionales de grafos. En particular, Wood (2002) usó una construcción para embebidos en libro que mantiene bajo el degree de cada vértice dentro de cada página, como parte de un método para incrustar grafos en una cuadrícula tridimensional de bajo volumen.[55]​

plegamiento de ARN

Un fragmento de telomerasa humana que muestra un pseudonudo. Si el fragmento se estira recto a lo largo del lomo de un libro de embebido, los pares de bases azules se pueden dibujar en dos subconjuntos que no se cruzan por encima y por debajo del lomo, lo que demuestra que este pseudonudo forma una estructura bisecundaria

En el estudio de cómo las moléculas Ácido ribonucleico se pliegan para formar su estructura, la forma estándar de nucleic acid secondary structure se puede describir en forma de diagrama como una cadena de bases (la secuencia de ARN misma), dibujada en una línea, junto con una colección de arcos sobre la línea que describe el par de basess de la estructura. Es decir, aunque estas estructuras en realidad tienen una forma tridimensional complicada, su conectividad (cuando existe una estructura secundaria) puede describirse mediante una estructura más abstracta, el embebido de un libro de una página. Sin embargo, no todos los pliegues del ARN se comportan de esta forma tan sencilla. Haslinger y Stadler (1999) ha propuesto una denominada "estructura bisecundaria" para ciertos pseudonudo de ARN que toma la forma de un libro de dos páginas embebido: la secuencia de ARN se dibuja nuevamente en una línea, pero los pares de bases se dibujan como arcos tanto arriba como abajo. esta línea. Para formar una estructura bisecundaria, un grafo debe tener un grado máximo de tres: cada base solo puede participar en un arco del diagrama, además de los dos enlaces a sus vecinos en la secuencia de bases. Las ventajas de esta formulación incluyen el hecho de que excluye estructuras que están realmente anudadas en el espacio y que coincide con la mayoría de los pseudonudos de ARN conocidos.[7]​

Debido a que el orden de la columna vertebral se conoce de antemano para esta aplicación, la prueba de la existencia de una estructura bisecundaria para un par de bases dado es sencilla. El problema de asignar vínculos a las dos páginas de manera compatible se puede formular como una instancia de 2-satisfiability o como un problema de prueba de bipartiteness de circle graph cuyos vértices son los pares de bases y cuyos vínculos describen cruces entre pares de bases.[7]​ De manera alternativa y más eficiente, como muestra Haslinger y Stadler (1999), existe una estructura bisecundaria si y solo si el "grafo de diagrama" de la entrada (un grafo formado conectando las bases en un ciclo en su orden de secuencia y sumando los pares de bases dados como vínculos) es un grafo plano.[7]​ Esta caracterización permite reconocer estructuras bisecundarias en complejidad temporal como una instancia de planarity testing.

Blin et al. (2007) usó la conexión entre las estructuras secundarias y los embebidos en libro como parte de una prueba de la calidad NP-hard de ciertos problemas en la comparación de estructuras secundarias de ARN.[64]​ Y si una estructura de ARN es terciaria en lugar de bisecundaria (es decir, si requiere más de dos páginas en su diagrama), determinar el número de página es nuevamente NP-difícil.[65]​

Teoría de la complejidad computacional

Pavan, Tewari y Vinodchandran (2012) utilizó el embebido de libros para estudiar el teoría de la complejidad computacional del problema reachability en grafo dirigido. Como han observado, la accesibilidad para grafos dirigidos de dos páginas se puede resolver en un espacio logarítmico no ambiguo (el análogo, para logarithmic space complexity, de la clase UP de problemas de tiempo polinomial no ambiguos). Sin embargo, la accesibilidad para grafos dirigidos de tres páginas requiere todo el poder de nondeterministic logarithmic space. Por lo tanto, los embebidos en libro parecen estar íntimamente conectadas con la distinción entre estas dos clases de complejidad.[66]​

La existencia de expander graph con un número de página constante[36]​ es el paso clave para demostrar que no existe una simulación en tiempo subcuadrático de non-deterministic Turing machine de dos cintas mediante máquinas de Turing no deterministas de una cinta.[67]​

Otras áreas de las matemáticas

McKenzie y Overbay (2010) estudia las aplicaciones del grosor de los libros en álgebra abstracta, utilizando grafos definidos a partir de los divisor de cero de un anillo local finito al crear un vértice para cada divisor de cero y una arista para cada par de valores cuyo producto es cero.[68]​

En una secuencia de varios artículos, Dynnikov ha estudiado los embebidos topológicas de libros de knots y links, demostrando que estas embebidos pueden describirse mediante una secuencia combinatoria de símbolos y que la equivalencia topológica de dos enlaces puede demostrarse mediante una secuencia de cambios locales en los embebidos.[69]​[70]​

Referencias

  1. ↑ a b Persinger, C. A. (1966), «Subsets of n-books in E3», Pacific Journal of Mathematics 18: 169-173, MR 0195077, doi:10.2140/pjm.1966.18.169 ..
  2. ↑ a b Atneosen, Gail Adele (1968), On the embeddability of compacta in n-books: intrinsic and extrinsic properties, Ph.D. thesis, Universidad Estatal de Míchigan, p. 79, MR 2617705 .. See also Atneosen, Gail H. (1972), «One-dimensional n-leaved continua», Fundamenta Mathematicae 74 (1): 43-45, MR 0293592, doi:10.4064/fm-74-1-43-45 ..
  3. ↑ Kainen, Paul C. (1974), «Some recent results in topological graph theory», en Bari, Ruth A.; Harary, Frank, eds., Graphs and Combinatorics (Proceedings of the Capital Conference on Graph Theory and Combinatorics at the George Washington University June 18–22, 1973), Lecture Notes in Mathematics 406, pp. 76-108 ..
  4. ↑ Ollmann, L. Taylor (1973), «On the book thicknesses of various graphs», en Hoffman, Frederick; Levow, Roy B.; Thomas, Robert S. D., eds., Proc. 4th Southeastern Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium VIII, p. 459 ..
  5. ↑ a b c Yannakakis, Mihalis (1989), «Embedding planar graphs in four pages», Journal of Computer and System Sciences 38: 36-67, doi:10.1016/0022-0000(89)90032-9 .
  6. ↑ a b c Yannakakis, Mihalis (1986), «Four pages are necessary and sufficient for planar graphs», Proceedings of the 18th ACM Symposium on Theory of Computing (STOC '86), pp. 104-108, ISBN 0-89791-193-8, S2CID 5359519, doi:10.1145/12130.12141 ..
  7. ↑ a b c d e Haslinger, Christian; Stadler, Peter F. (1999), «RNA structures with pseudo-knots: Graph-theoretical, combinatorial, and statistical properties», Bulletin of Mathematical Biology 61 (3): 437-467, PMC 7197269, PMID 17883226, doi:10.1006/bulm.1998.0085 ..
  8. ↑ Hales, T. C. (1997), «Sphere packings. II», Discrete and Computational Geometry 18 (2): 135-149, MR 1455511, doi:10.1007/PL00009312 ..
  9. ↑ En inglés, los términos "spine" y "pages" es más estándar en los enfoques teóricos de grafos modernos sobre el tema. Para conocer más en detalle esta terminología, véase Persinger (1966).
  10. ↑ a b c d e f g Bernhart, Frank R.; Kainen, Paul C. (1979), «The book thickness of a graph», Journal of Combinatorial Theory, Series B 27 (3): 320-331, MR 0554297, doi:10.1016/0095-8956(79)90021-2 ..
  11. ↑ Shahrokhi, Farhad; Székely, László A.; Sýkora, Ondrej; Vrťo, Imrich (1996), «The book crossing number of a graph», Journal of Graph Theory 21 (4): 413-424, MR 1377615, doi:10.1002/(SICI)1097-0118(199604)21:4<413::AID-JGT7>3.3.CO;2-5 ..
  12. ↑ a b c Heath, Lenwood S. (1987), «Embedding outerplanar graphs in small books», SIAM Journal on Algebraic and Discrete Methods 8 (2): 198-218, MR 881181, doi:10.1137/0608018 ..
  13. ↑ Stöhr, Elena (1988), «A trade-off between page number and page width of book embeddings of graphs», Information and Computation 79 (2): 155-162, MR 968104, doi:10.1016/0890-5401(88)90036-3 ..
  14. ↑ Stöhr, Elena (1991), «The pagewidth of trivalent planar graphs», Discrete Mathematics 89 (1): 43-49, MR 1108073, doi:10.1016/0012-365X(91)90398-L ..
  15. ↑ a b c Enomoto, Hikoe; Miyauchi, Miki Shimabara (1999), «Embedding graphs into a three page book with O(M log N) crossings of edges over the spine», SIAM Journal on Discrete Mathematics 12 (3): 337-341, MR 1710241, doi:10.1137/S0895480195280319 ..
  16. ↑ a b c Blankenship, Robin; Oporowski, Bogdan (1999), Drawing Subdivisions Of Complete And Complete Bipartite Graphs On Books, Technical Report 1999-4, Department of Mathematics, Louisiana State University, «citeseerx: 10.1.1.36.4358» ..
  17. ↑ Enomoto, Hikoe; Miyauchi, Miki Shimabara; Ota, Katsuhiro (1999), «Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph», Discrete Applied Mathematics 92 (2–3): 149-155, MR 1697548, doi:10.1016/S0166-218X(99)00044-X ..
  18. ↑ Ábrego, Bernardo M.; Aichholzer, Oswin; Fernández-Merchant, Silvia; Ramos, Pedro; Salazar, Gelasio (2012), «The 2-page crossing number of Kn (extended abstract)», Proceedings of the 28th Annual Symposium on Computational Geometry (SCG'12), ACM, New York, pp. 397-403, MR 3050657, S2CID 8344088, doi:10.1145/2261250.2261310 ..
  19. ↑ Para obtener resultados adicionales sobre el grosor del libro de gráficos bipartitos completos, consúltese Enomoto, Hikoe; Nakamigawa, Tomoki; Ota, Katsuhiro (1997), «On the pagenumber of complete bipartite graphs», Journal of Combinatorial Theory, Series B 71 (1): 111-120, MR 1469870, doi:10.1006/jctb.1997.1773 .; de Klerk, Etienne; Pasechnik, Dmitrii V.; Salazar, Gelasio (2014), «Book drawings of complete bipartite graphs», Discrete Applied Mathematics 167: 80-93, MR 3166108, S2CID 40920263, arXiv:1210.2918, doi:10.1016/j.dam.2013.11.001 ..
  20. ↑ Sperfeld, Konrad (2013), «On the page number of complete odd-partite graphs», Discrete Mathematics 313 (17): 1689-1696, MR 3061004, doi:10.1016/j.disc.2013.04.028 ..
  21. ↑ Hasunuma, Toru; Shibata, Yukio (1997), «Embedding de Bruijn, Kautz and shuffle-exchange networks in books», Discrete Applied Mathematics 78 (1–3): 103-116, MR 1475820, doi:10.1016/S0166-218X(97)00009-7 .; Tanaka, Yuuki; Shibata, Yukio (2010), «On the pagenumber of the cube-connected cycles», Mathematics in Computer Science 3 (1): 109-117, MR 2596254, S2CID 11830437, doi:10.1007/s11786-009-0012-y .. See also Obrenić, Bojana (1993), «Embedding de Bruijn and shuffle-exchange graphs in five pages», SIAM Journal on Discrete Mathematics 6 (4): 642-654, MR 1241401, doi:10.1137/0406049 ..
  22. ↑ Bekos, Michael A.; Gronemann, Martin; Raftopoulou, Chrysanthi N. (2014), «Two-page book embeddings of 4-planar graphs», Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science, Leibniz International Proceedings in Informatics (LIPIcs) 25, pp. 137-148, ISBN 9783939897651, arXiv:1401.0684, doi:10.4230/LIPIcs.STACS.2014.137 ..
  23. ↑ Heath, Lenny (1984), «Embedding planar graphs In seven pages», Proceedings of the 25th Annual Symposium on Foundations of Computer Science, pp. 74-83, doi:10.1109/SFCS.1984.715903 ..
  24. ↑ a b Bekos, Michael A.; Kaufmann, Micheal; Klute, Fabian; Pupyrev, Sergey; Raftopoulou, Chrysanthi; Ueckerdt, Torsten (2020), «Four Pages Are Indeed Necessary for Planar Graphs», Journal of Computational Geomerty 1 (11): 332-353, arXiv:2004.07630 ..
  25. ↑ a b c Eppstein, David (2001), Separating geometric thickness from book thickness, Bibcode:2001math......9195E, arXiv:math.CO/0109195 ..
  26. ↑ Dujmović, Vida; Eppstein, David; Hickingbotham, Robert; Morin, Pat; Wood, David R. (August 2021), «Stack-number is not bounded by queue-number», Combinatorica, arXiv:2011.04195, doi:10.1007/s00493-021-4585-7 .
  27. ↑ a b Dujmović, Vida; Wood, David R. (2007), «Graph treewidth and geometric thickness parameters», Discrete and Computational Geometry 37 (4): 641-670, S2CID 9141367, arXiv:math/0503553, doi:10.1007/s00454-007-1318-7 ..
  28. ↑ Ganley, Joseph L.; Heath, Lenwood S. (2001), «The pagenumber of k-trees is O(k)», Discrete Applied Mathematics 109 (3): 215-221, MR 1818238, doi:10.1016/S0166-218X(00)00178-5 ..
  29. ↑ Malitz, Seth M. (1994), «Graphs with E edges have pagenumber O(√E)», Journal of Algorithms 17 (1): 71-84, MR 1279269, doi:10.1006/jagm.1994.1027 ..
  30. ↑ Malitz, Seth M. (1994), «Genus g graphs have pagenumber O(√g)», Journal of Algorithms 17 (1): 85-109, MR 1279270, doi:10.1006/jagm.1994.1028 ..
  31. ↑ a b c d Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics 28, Springer, pp. 321-328, ISBN 978-3-642-27874-7, MR 2920058, doi:10.1007/978-3-642-27875-4 ..
  32. ↑ Blankenship, R. (2003), Book Embeddings of Graphs, Ph.D. thesis, Department of Mathematics, Louisiana State University .. Citado por Nešetřil y Ossona de Mendez (2012).
  33. ↑ Bekos, Michael A.; Bruckdorfer, Till; Kaufmann, Michael; Raftopoulou, Chrysanthi (2015), «1-Planar graphs have constant book thickness», Algorithms – ESA 2015, Lecture Notes in Computer Science 9294, Springer, pp. 130-141, doi:10.1007/978-3-662-48350-3_12 ..
  34. ↑ a b Bekos, Michael; Kaufmann, Michael; Zielke, Christian (2015), «The book embedding problem from a SAT-solving perspective», Proc. 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015), pp. 113-125 ..
  35. ↑ Barát, János; Matoušek, Jiří; Wood, David R. (2006), «Bounded-degree graphs have arbitrarily large geometric thickness», Electronic Journal of Combinatorics 13 (1): R3, MR 2200531, doi:10.37236/1029 ..
  36. ↑ a b Dujmović, Vida; Sidiropoulos, Anastasios; Wood, David R. (2015), 3-Monotone Expanders, Bibcode:2015arXiv150105020D, arXiv:1501.05020 ., mejorando un resultado anterior que mostraba la existencia de expansores con número de página constante de Bourgain, Jean (2009), «Expanders and dimensional expansion», Comptes Rendus Mathématique 347 (7–8): 357-362, MR 2537230, doi:10.1016/j.crma.2009.02.009 .; Bourgain, Jean; Yehudayoff, Amir (2013), «Expansion in and monotone expanders», Geometric and Functional Analysis 23 (1): 1-41, MR 3037896, S2CID 121554827, doi:10.1007/s00039-012-0200-9 .. See also Galil, Zvi; Kannan, Ravi; Szemerédi, Endre (1989), «On 3-pushdown graphs with large separators», Combinatorica 9 (1): 9-19, MR 1010295, S2CID 37506294, doi:10.1007/BF02122679 .; Dvir, Zeev; Wigderson, Avi (2010), «Monotone expanders: constructions and applications», Theory of Computing 6: 291-308, MR 2770077, doi:10.4086/toc.2010.v006a012 ..
  37. ↑ Heath, Lenwood S.; Rosenberg, Arnold L. (1992), «Laying out graphs using queues», SIAM Journal on Computing 21 (5): 927-958, MR 1181408, doi:10.1137/0221055 ..
  38. ↑ Dujmović, Vida; Wood, David R. (2004), «On linear layouts of graphs», Discrete Mathematics & Theoretical Computer Science 6 (2): 339-357, MR 2081479 ..
  39. ↑ a b c Chung, Fan R. K.; Leighton, Frank Thompson; Rosenberg, Arnold L. (1987), «Embedding graphs in books: A layout problem with applications to VLSI design», SIAM Journal on Algebraic and Discrete Methods 8 (1): 33-58, doi:10.1137/0608002 ..
  40. ↑ Unger, Walter (1992), «The complexity of colouring circle graphs», STACS 92: 9th Annual Symposium on Theoretical Aspects of Computer Science, Cachan, France, February 13–15, 1992, Proceedings, Lecture Notes in Computer Science 577, Berlin: Springer, pp. 389-400, doi:10.1007/3-540-55210-3_199 ..
  41. ↑ Unger, Walter (1988), «On the k-colouring of circle-graphs», Proceedings of the 5th Symposium on Theoretical Aspects of Computer Science (STACS '88), Lecture Notes in Computer Science 294, Springer-Verlag, pp. 61-72, doi:10.1007/BFb0035832 ..
  42. ↑ a b c d Masuda, Sumio; Nakajima, Kazuo; Kashiwabara, Toshinobu; Fujisawa, Toshio (1990), «Crossing minimization in linear embeddings of graphs», IEEE Transactions on Computers 39 (1): 124-127, MR 1032144, doi:10.1109/12.46286 ..
  43. ↑ Garey, M. R.; Johnson, D. S.; Miller, G. L.; Papadimitriou, C. H. (1980), «The complexity of coloring circular arcs and chords», SIAM Journal on Algebraic and Discrete Methods 1 (2): 216-227, MR 578325, doi:10.1137/0601025 ..
  44. ↑ a b c Hong, Seok-Hee; Nagamochi, Hiroshi (2009), Two-page book embedding and clustered graph planarity, Technical report (2009-004 edición), Dept. of Applied Mathematics and Physics, University of Kyoto, Japan ..
  45. ↑ Angelini, Patrizio; Di Bartolomeo, Marco; Di Battista, Giuseppe (2013), «Implementing a partitioned 2-page book embedding testing algorithm», Graph Drawing: 20th International Symposium, GD 2012, Redmond, WA, USA, September 19–21, 2012, Revised Selected Papers, Lecture Notes in Computer Science 7704, Springer, pp. 79-89, MR 3067219, S2CID 15360191, arXiv:1209.0598, doi:10.1007/978-3-642-36763-2_8 ..
  46. ↑ Nešetřil y Ossona de Mendez (2012), Corollary 18.1, p. 401.
  47. ↑ Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2008), «Grad and classes with bounded expansion. II. Algorithmic aspects», European Journal of Combinatorics 29 (3): 777-791, MR 2397336, S2CID 1139740, arXiv:math/0508324, doi:10.1016/j.ejc.2006.07.014 ..
  48. ↑ Nešetřil y Ossona de Mendez (2012), Theorem 18.7, p. 405.
  49. ↑ Rosenberg, Arnold L. (1986), «Book embeddings and wafer-scale integration», Proceedings of the seventeenth Southeastern international conference on combinatorics, graph theory, and computing (Boca Raton, Fla., 1986), Congressus Numerantium 54, pp. 217-224, MR 885282 ..
  50. ↑ Knuth, Donald E. (1968), The Art Of Computer Programming Vol. 1, Boston: Addison-Wesley, Section 2.2.1, Exercises 4 and 5, ISBN 0-201-89683-4, MR 0286317, OCLC 155842391 ..
  51. ↑ Kainen, Paul C. (1990), «The book thickness of a graph. II», Proceedings of the Twentieth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1989), Congressus Numerantium 71, pp. 127-132, MR 1041623 ..
  52. ↑ a b Wattenberg, M. (2002), «Arc diagrams: visualizing structure in strings», Proceedings of IEEE Symposium on Information Visualization (INFOVIS 2002), pp. 110-116, S2CID 881989, doi:10.1109/INFVIS.2002.1173155 ..
  53. ↑ a b c Baur, Michael; Brandes, Ulrik (2005), «Crossing reduction in circular layouts», en van Leeuwen, Jan, ed., 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, pp. 332-343, doi:10.1007/978-3-540-30559-0_28 ..
  54. ↑ a b Angelini, Patrizio; Di Battista, Giuseppe; Frati, Fabrizio; Patrignani, Maurizio; Rutter, Ignaz (2012), «Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph», Journal of Discrete Algorithms 14: 150-172, MR 2922068, doi:10.1016/j.jda.2011.12.015 ..
  55. ↑ a b 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 2265, Springer, Berlin, pp. 312-327, MR 1962433, doi:10.1007/3-540-45848-4_25 ..
  56. ↑ Saaty, Thomas L. (1964), «The minimum number of intersections in complete graphs», Proceedings of the National Academy of Sciences 52 (3): 688-690, Bibcode:1964PNAS...52..688S, MR 0166772, PMC 300329, PMID 16591215, doi:10.1073/pnas.52.3.688 ..
  57. ↑ Nicholson, T. A. J. (1968), «Permutation procedure for minimising the number of crossings in a network», Proceedings of the Institution of Electrical Engineers 115: 21-26, MR 0311416, doi:10.1049/piee.1968.0004 ..
  58. ↑ Miyauchi, Miki (2006), «Topological book embedding of bipartite graphs», 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 ..
  59. ↑ Giordano, Francesco; Liotta, Giuseppe; Mchedlidze, Tamara; Symvonis, Antonios (2007), «Computing upward topological book embeddings of upward planar digraphs», Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17–19, 2007, Proceedings, Lecture Notes in Computer Science 4835, Springer, pp. 172-183, doi:10.1007/978-3-540-77120-3_17 ..
  60. ↑ He, Hongmei; Sykora, Ondrej (2004), «New circular drawing algorithms», Proceedings of the Workshop on Information Technologies – Applications and Theory (ITAT), Slovakia, September 15–19, 2004 ..
  61. ↑ 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 903, Springer, pp. 256-268, doi:10.1007/3-540-59071-4_53 ..
  62. ↑ Bannister, Michael J.; Eppstein, David; Simons, Joseph A. (2013), «Fixed parameter tractability of crossing minimization of almost-trees», Graph Drawing: 21st International Symposium, GD 2013, vínculoaux, France, September 23–25, 2013, Revised Selected Papers, Lecture Notes in Computer Science 8242, pp. 340-351, S2CID 10142319, arXiv:1308.5741, doi:10.1007/978-3-319-03841-4_30 ..
  63. ↑ Bannister, Michael J.; Eppstein, David (2014), «Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth», Proc. 22nd Int. Symp. Graph Drawing (GD 2014), Lecture Notes in Computer Science 8871, Springer-Verlag, pp. 210-221, MR 3333228, arXiv:1408.6321, doi:10.1007/978-3-662-45803-7_18 ..
  64. ↑ Blin, Guillaume; Fertin, Guillaume; Rusu, Irena; Sinoquet, Christine (2007), «Extending the hardness of RNA secondary structure comparison», Combinatorics, Algorithms, Probabilistic and Experimental Methodologies: First International Symposium, ESCAPE 2007, Hangzhou, China, April 7-9, 2007, Revised Selected Papers, Lecture Notes in Computer Science 4614, pp. 140-151, doi:10.1007/978-3-540-74450-4_13 ..
  65. ↑ Clote, Peter; Dobrev, Stefan; Dotu, Ivan; Kranakis, Evangelos; Krizanc, Danny; Urrutia, Jorge (2012), «On the page number of RNA secondary structures with pseudoknots», Journal of Mathematical Biology 65 (6–7): 1337-1357, PMID 22159642, S2CID 8700502, doi:10.1007/s00285-011-0493-6 ..
  66. ↑ Pavan, A.; Tewari, Raghunath; Vinodchandran, N. V. (2012), «On the power of unambiguity in log-space», Computational Complexity 21 (4): 643-670, MR 2988774, S2CID 8666071, arXiv:1001.2034, doi:10.1007/s00037-012-0047-3 ..
  67. ↑ Galil, Zvi; Kannan, Ravi; Szemerédi, Endre (1989), «On nontrivial separators for k-page graphs and simulations by nondeterministic one-tape Turing machines», Journal of Computer and System Sciences 38 (1): 134-149, doi:10.1016/0022-0000(89)90036-6 ..
  68. ↑ McKenzie, Thomas; Overbay, Shannon (2010), «Book embeddings and zero divisors», Ars Combinatoria 95: 55-63, MR 2656248 ..
  69. ↑ Dynnikov, I. A. (1999), «Three-page approach to knot theory. Coding and local motions», Rossiĭskaya Akademiya Nauk 33 (4): 25-37, 96, MR 1746427, S2CID 121089736, doi:10.1007/BF02467109 ..
  70. ↑ Dynnikov, I. A. (2001), «A new way to represent links, one-dimensional formalism and untangling technology», Acta Applicandae Mathematicae 69 (3): 243-283, MR 1885279, S2CID 116488382, doi:10.1023/A:1014299416618 ..
Obtenido de «https://es.wikipedia.org/eswiki/w/index.php?title=Embebido_en_libro&oldid=145743090»