En teoría de grafos , la incrustación de un libro es una generalización de la incrustación plana de un gráfico a incrustaciones en un libro , una colección de semiplanos que tienen todos la misma línea como límite. Por lo general, se requiere que los vértices del gráfico se encuentren en esta línea límite, llamada columna vertebral , y que los bordes permanezcan dentro de un único semiplano. El espesor del libro de un gráfico es el menor número posible de semiplanos para cualquier incrustación del gráfico en un libro. El grosor del libro también se denomina número de página , número de pila o grosor exterior fijo . Las incrustaciones de libros también se han utilizado para definir otras invariantes de gráficos, incluido el ancho de página y el número de cruce de libros.
Cada gráfico con n vértices tiene un espesor de libro como máximo , y esta fórmula da el espesor de libro exacto para gráficos completos . Los gráficos con un grosor de libro uno son los gráficos del plano exterior . Las gráficas con espesor de libro como máximo dos son las gráficas subhamiltonianas , que son siempre planas ; De manera más general, cada gráfico plano tiene un grosor de libro como máximo de cuatro. Todas las familias de gráficos menores cerrados , y en particular los gráficos con ancho de árbol acotado o género acotado , también tienen espesor de libro acotado. Es NP-difícil determinar el grosor exacto del libro de un gráfico determinado, conociendo o sin un orden de vértices fijo a lo largo del lomo del libro. Probar la existencia de un libro de tres páginas incrustado de un gráfico, dado un orden fijo de los vértices a lo largo del lomo de la incrustación, tiene una complejidad computacional desconocida: no se sabe que se pueda resolver en tiempo polinómico ni que sea NP-duro .
Una de las motivaciones originales para estudiar las incrustaciones de libros involucró aplicaciones en el diseño VLSI , en las que los vértices de una incrustación de libros representan componentes de un circuito y los cables representan conexiones entre ellos. La incrustación de libros también tiene aplicaciones en el dibujo de gráficos , donde dos de los estilos de visualización estándar para gráficos, diagramas de arco y diseños circulares , se pueden construir utilizando incrustaciones de libros.
En la planificación del 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 gráfico, con aristas que conectan diferentes pares de fuente-destino. Se puede utilizar una incorporación de este gráfico en un libro 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 de fases de señal posible. En los problemas de bioinformática relacionados con la estructura de plegado del ARN , las incrustaciones de libros de una sola página representan formas clásicas de estructura secundaria de ácido nucleico , y las incrustaciones de libros de dos páginas representan pseudonudos . Otras aplicaciones de las incrustaciones de libros incluyen el álgebra abstracta y la teoría de nudos .
La noción de libro, como espacio topológico, fue definida por CA Persinger y Gail Atneosen en la década de 1960. [1] [2] Como parte de este trabajo, Atneosen ya consideró la incorporación de gráficos en libros. Las incrustaciones que estudió utilizaron la misma definición que las incrustaciones de gráficos en cualquier otro espacio topológico: los vértices están representados por puntos distintos, las aristas están representadas por curvas y la única forma en que dos aristas pueden cruzarse 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 incrustación más restringido que llegó a utilizarse en la mayoría de las investigaciones posteriores. En su formulación, los vértices del gráfico deben ubicarse a lo largo del lomo del libro, y cada borde debe estar en una sola página. [3] [4] Los hitos importantes en el desarrollo posterior de las incrustaciones de libros incluyen la prueba de Mihalis Yannakakis a fines de la década de 1980 de que los gráficos planos tienen un espesor de libro de como máximo cuatro, [5] [6] y el descubrimiento a fines de la década de 1990 de cerca Conexiones entre incrustaciones de libros y bioinformática . [7]
Un libro es un tipo particular de espacio topológico , también llamado abanico de semiplanos. [1] [8] Consta de una sola línea ℓ , llamada lomo o lomo del libro, junto con una colección de uno o más semiplanos , llamados páginas u hojas del libro, [9] cada uno con el columna vertebral como límite. Los libros con un número finito de páginas se pueden incrustar en un espacio tridimensional, por ejemplo, eligiendo ℓ como el eje z de un sistema de coordenadas cartesiano y eligiendo las páginas como los k semiplanos cuyo ángulo diédrico con respecto al El plano xz es un múltiplo entero de 2 π / k . [10]
Un libro que dibuja un gráfico finito G en un libro B es un dibujo de G en B tal que cada vértice de G se dibuja como un punto en la columna vertebral de B , y cada arista de G se dibuja como una curva que se encuentra dentro de un una sola página de B . El número de cruces de un libro de k páginas de G es el número mínimo de cruces en un dibujo de un libro de k páginas. [11]
Un libro que incorpora G en B es un dibujo de un libro que forma un gráfico que incorpora G en B. Es decir, es un dibujo de libro de G sobre B que no tiene cruces de bordes. Cada gráfico finito tiene un libro incrustado en un libro con un número suficientemente grande de páginas. Por ejemplo, siempre es posible incrustar cada borde del gráfico 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 necesarias para la incrustación de un libro de G. Otro parámetro que mide la calidad de la incrustación de un libro, más allá de su número de páginas, es su ancho de página . Esto se define de manera análoga al ancho de corte como el número máximo de bordes que puede cruzar un rayo perpendicular al lomo dentro de una sola página. De manera equivalente (para incrustaciones de libros en las que cada borde se dibuja como una curva monótona), es el tamaño máximo de un subconjunto de bordes dentro de una sola página de modo que los intervalos definidos en el lomo por pares de puntos finales de los bordes se intersectan entre sí. . [12] [13] [14]
Es crucial para estas definiciones que los bordes solo puedan permanecer dentro de una sola página del libro. Como ya observó Atneosen, si los bordes pueden pasar de una página a otra a lo largo del lomo del libro, entonces cada gráfico puede integrarse en un libro de tres páginas. [15] [2] [16] Para la incrustación de un libro topológico de tres páginas en el que se permiten cruces de lomos, cada gráfico se puede incrustar con como máximo un número logarítmico de cruces de lomos por borde, [15] y algunos gráficos necesitan esto muchos cruces de columna. [17]
Como se muestra en la primera figura, el espesor del libro del gráfico completo K 5 es tres: como gráfico no plano su espesor del libro es mayor que dos, pero existe un libro incrustado con tres páginas. De manera más general, el espesor del libro de cada gráfico completo con n ≥ 4 vértices es exactamente . Este resultado también proporciona un límite superior para el espesor de libro máximo posible de cualquier gráfico de n -vértices. [10]
El número de cruce de dos páginas del gráfico completo K n es
coincidiendo con una conjetura aún no probada de Anthony Hill sobre cuál debería ser el número de cruce ilimitado de este gráfico. Es decir, si la conjetura de Hill es correcta, entonces el dibujo de este gráfico que minimiza el número de cruces es un dibujo de dos páginas. [18]
El espesor del libro del gráfico bipartito completo K a , b es como máximo min( a , b ) . Para construir un dibujo con este grosor de libro, para cada vértice en el lado menor de la bipartición, se pueden colocar los bordes incidentes con ese vértice en su propia página. Este límite no siempre es estricto; Por ejemplo, K 4,4 tiene un grosor de libro de tres, no de cuatro. Sin embargo, cuando los dos lados de la gráfica están muy desequilibrados, con b > a ( a − 1 ) , el espesor del libro de K a , b es exactamente a . [10] [19]
Para el gráfico de Turán T ( kr , r ) (un gráfico multipartito completo K k , k ,... formado a partir de r conjuntos independientes de k vértices por conjunto independiente, con un borde entre cada dos vértices de diferentes conjuntos independientes) el espesor del libro está intercalado entre
y cuando r es impar, el límite superior se puede mejorar a
El espesor del libro de las gráficas binarias de De Bruijn , las gráficas de intercambio aleatorio y los ciclos conectados por cubos (cuando estas gráficas son lo suficientemente grandes como para no ser planas) es exactamente tres. [21]
El espesor del libro de un gráfico dado G es como máximo uno si y sólo si G es un gráfico plano externo . Un gráfico plano exterior es un gráfico que tiene una incrustación plana en la que todos los vértices pertenecen a la cara exterior de la incrustación. Para un gráfico de este tipo, colocar los vértices en el mismo orden a lo largo del lomo tal como aparecen en la cara exterior proporciona un libro de una página incrustado del gráfico dado. (Un punto de articulación del gráfico aparecerá necesariamente más de una vez en el orden cíclico de los vértices alrededor de la cara exterior, pero sólo una de esas copias debe incluirse en la incrustación del libro). Por el contrario, la incrustación de un libro de una página es automáticamente una incrustación en el plano exterior. Porque, si un gráfico está incrustado en una sola página y se adjunta otro semiplano al lomo para extender su página a un plano completo, entonces la cara exterior de la incrustación incluye todo el semiplano agregado y todos los vértices se encuentran en esta cara exterior. [10] [12]
Cada incrustación de un libro de dos páginas es un caso especial de incrustación plana, porque la unión de dos páginas de un libro es un espacio topológicamente equivalente al plano completo. Por lo tanto, cada gráfico con un grosor de libro dos es automáticamente un gráfico plano . Más precisamente, el espesor del libro de un gráfico G es como máximo dos si y sólo si G es un subgrafo de un gráfico plano que tiene un ciclo hamiltoniano . [10] Si a un gráfico se le da una incrustación de dos páginas, se puede aumentar a un gráfico hamiltoniano plano agregando (en cualquier página) bordes adicionales entre dos vértices consecutivos cualesquiera a lo largo del lomo que no sean adyacentes, y entre el primero. y últimos vértices de la columna. El gráfico de Goldner-Harary proporciona un ejemplo de un gráfico plano que no tiene un espesor de libro dos: es un gráfico plano máximo , por lo que no es posible agregarle aristas mientras se conserva la planaridad, y no tiene un ciclo hamiltoniano. . [10] Debido a esta caracterización por ciclos hamiltonianos, los gráficos que tienen incrustaciones de libros de dos páginas también se conocen como gráficos subhamiltonianos . [12]
Todos los gráficos planos cuyo grado máximo es como máximo cuatro tienen un espesor de libro como máximo dos. [22] Los 3 árboles planos tienen un grosor de libro como máximo de tres. [23] De manera más general, todos los gráficos planos tienen un grosor de libro cuatro. [5] [6] [24] Mihalis Yannakakis afirmó en 1986 [6] que existen algunos gráficos planos que tienen un grosor de libro exactamente cuatro. Sin embargo, una prueba detallada de esta afirmación, anunciada en un artículo de revista posterior, [5] no se conoció hasta 2020, cuando Bekos et al. [24] presentaron gráficos planos con un ancho de árbol de 4 que requieren cuatro páginas en cualquier libro incrustado.
Subdividir cada borde de un gráfico en trayectorias de dos bordes, agregando nuevos vértices dentro de cada borde, a veces puede aumentar el grosor del libro. Por ejemplo, el gráfico de diamante tiene un espesor de libro uno (es plano externo) pero su subdivisión tiene un espesor de libro dos (es plano y subhamiltoniano pero no plano externo). Sin embargo, este proceso de subdivisión a veces también puede reducir significativamente el grosor del libro del gráfico subdividido. Por ejemplo, el espesor del libro del gráfico completo K n es proporcional a su número de vértices, pero subdividir cada una de sus aristas en una trayectoria de dos aristas produce una subdivisión cuyo espesor del libro es mucho menor, sólo . [25] A pesar de la existencia de ejemplos como este, Blankenship y Oporowski (1999) conjeturaron que el espesor del libro de una subdivisión no puede ser mucho menor que el del gráfico original. Específicamente, conjeturaron que existe una función f tal que, para cada gráfico G y para el gráfico H formado reemplazando cada borde en G por una trayectoria de dos bordes, si el espesor del libro de H es t entonces el espesor del libro de G es como máximo f ( t ) . [16] Su conjetura resultó ser falsa: los gráficos formados por productos cartesianos de estrellas y mosaicos triangulares tienen un espesor de libro ilimitado, pero subdividir sus bordes en caminos de seis bordes reduce su espesor de libro a tres. [26]
El grosor del libro está relacionado con el grosor , la cantidad de gráficos planos necesarios para cubrir los bordes del gráfico dado. Un gráfico G tiene espesor θ si se puede dibujar en el plano, y sus aristas coloreadas con θ colores, de tal manera que las aristas del mismo color entre sí no se crucen. De manera análoga, un gráfico G tiene un espesor de libro θ si se puede dibujar en un semiplano , con sus vértices en el límite del semiplano, con sus bordes coloreados con θ colores sin cruce entre dos bordes del mismo color. En esta formulación del grosor del libro, los colores de los bordes corresponden a las páginas del libro incrustado. Sin embargo, espesor y espesor de libro pueden ser muy diferentes entre sí: existen gráficas ( subdivisiones de gráficas completas ) que tienen espesor de libro ilimitado, [25] [15] [16] a pesar de tener espesor dos. [25]
Los gráficos de ancho de árbol k tienen un grosor de libro como máximo k + 1 [27] [28] y este límite es ajustado para k > 2 . [27] Las gráficas con m aristas tienen espesor de libro , [29] y las gráficas de género g tienen espesor de libro . [30] De manera más general, cada familia de gráficos menores cerrados tiene un grosor de libro limitado. [31] [32] Por otro lado, los gráficos uniplanares , que no están cerrados bajo menores, [31] también tienen un grosor de libro limitado, [33] pero algunos gráficos uniplanares incluyen K 2,2,2, 2 tienen un grosor de libro de al menos cuatro. [34]
Cada menor poco profundo de un gráfico de espesor de libro acotado es un gráfico disperso , cuya relación de aristas a vértices está acotada por una constante que depende sólo de la profundidad del menor y del espesor del libro. Es decir, en la terminología de Nešetřil & Ossona de Méndez (2012), las gráficas de espesor de libro acotado tienen expansión acotada . [31] Sin embargo, incluso las gráficas de grado acotado , un requisito mucho más estricto que tener expansión acotada, pueden tener un espesor de libro ilimitado. [35]
Debido a que las gráficas de espesor de libro dos son gráficas planas, obedecen al teorema del separador plano : tienen separadores, subconjuntos de vértices cuya eliminación divide la gráfica en partes con como máximo 2 n /3 vértices cada una, con solo vértices en el separador. Aquí, n se refiere al número de vértices del gráfico. Sin embargo, existen gráficos de espesor de libro tres que no tienen separadores de tamaño sublineal. [36]
Los bordes dentro de una sola página de la incrustación de un libro se comportan de alguna manera como una estructura de datos de pila . Esto se puede formalizar considerando una secuencia arbitraria de operaciones de empujar y sacar en una pila, y formando un gráfico en el que las operaciones de la pila corresponden a los vértices del gráfico, colocados en orden secuencial a lo largo del lomo de un libro incrustado. Luego, si uno dibuja un borde de cada operación pop que saca un objeto x de la pila, a la operación push anterior que empujó x , el gráfico resultante tendrá automáticamente una incrustación de una página. Por este motivo, al número de página de un gráfico también se le ha llamado número de pila . De la misma manera, se puede considerar una secuencia arbitraria de operaciones de poner y quitar la cola de una estructura de datos en cola , y formar un gráfico que tenga estas operaciones como vértices, colocados en orden en el lomo de una sola página, con un borde entre cada uno. operación de puesta en cola y la correspondiente retirada de cola. Luego, en este gráfico, cada dos bordes se cruzarán o cubrirán intervalos separados en la columna. Por analogía, los investigadores han definido una incrustación en cola de un gráfico como una incrustación en un libro topológico de modo que cada vértice se encuentra en el lomo, cada borde se encuentra en una sola página y cada dos bordes en la misma página se cruzan o cubren de forma separada. intervalos en la columna. El número mínimo de páginas necesarias para la incrustación de un gráfico en cola se denomina número de cola . [31] [37] [38]
Encontrar el grosor del libro de una gráfica es NP-difícil . Esto se desprende del hecho de que encontrar ciclos hamiltonianos en gráficos planos máximos es NP-completo . [39] En un gráfico plano máximo, el espesor del libro es dos si y sólo si existe un ciclo hamiltoniano. Por lo tanto, también es NP-completo probar si el espesor del libro de un gráfico plano máximo dado es dos. [40]
Si el orden de los vértices de un gráfico a lo largo del lomo de una incrustación es fijo, entonces se puede encontrar una incrustación de dos páginas (si existe) en tiempo lineal , como un ejemplo de prueba de planaridad para un gráfico formado aumentando el valor dado. gráfico con un ciclo que conecta los vértices en el orden de su columna. [7] Unger (1992) afirmó que encontrar incrustaciones de tres páginas con un orden de lomo fijo también se puede realizar en tiempo polinómico, aunque su artículo sobre este resultado omite muchos detalles. [41] Sin embargo, para gráficos que requieren cuatro o más páginas, el problema de encontrar una incrustación 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 colorear gráficos circulares , los gráficos de intersección de cuerdas de un círculo . Dado un gráfico G con un orden de columna fijo para sus vértices, dibujar estos vértices en el mismo orden alrededor de un círculo y dibujar los bordes de G como segmentos de línea produce una colección de cuerdas que representan G. Luego se puede formar un gráfico circular que tenga las cuerdas de este diagrama como vértices y los pares de cuerdas que se cruzan como aristas. Una coloración del gráfico circular representa una partición de los bordes de G en subconjuntos que se pueden dibujar sin cruzar en una sola página. Por tanto, una coloración óptima equivale a una incrustación óptima del libro. Dado que la coloración de un gráfico circular con cuatro o más colores es NP-difícil, y dado que cualquier gráfico circular se puede formar de esta manera a partir de algún problema de incrustación de libros, se deduce que la incrustación óptima de un libro también es NP-difícil. [42] [43] [44] Para un orden de vértice fijo en el lomo de un dibujo de 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. [43]
Si se desconoce el orden de los lomos pero se proporciona una partición de los bordes en dos páginas, entonces es posible encontrar una incrustación de 2 páginas (si existe) en tiempo lineal mediante un algoritmo basado en árboles SPQR . [45] [46] Sin embargo, es NP-completo encontrar una incrustación de 2 páginas cuando no se conoce el orden del lomo ni la partición del borde. Encontrar el número de cruce de libros de un gráfico también es NP-difícil, debido a la integridad NP 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 del isomorfismo del subgrafo , de encontrar si existe un gráfico patrón de tamaño acotado como subgrafo de un gráfico más grande, se puede resolver en tiempo lineal cuando el gráfico más grande tiene un espesor de libro acotado. Lo mismo ocurre para detectar si el gráfico de patrón es un subgrafo inducido del gráfico más grande o si tiene un homomorfismo gráfico con respecto al gráfico más grande. [47] [48] Por la misma razón, el problema de probar si una gráfica del grosor de un libro acotado obedece a una fórmula dada de lógica de primer orden es manejable con parámetros fijos . [49]
Bekos, Kaufmann y Zielke (2015) describen un sistema para encontrar incrustaciones óptimas de libros transformando el problema en una instancia del problema de satisfacibilidad booleano y aplicando un solucionador SAT al problema resultante. Afirman que su sistema es capaz de encontrar una incrustación óptima para gráficos planos máximos de 400 vértices en aproximadamente 20 minutos. [34]
Una de las principales motivaciones para estudiar la integración de libros citada por Chung, Leighton y Rosenberg (1987) implica una aplicación en el diseño VLSI a la organización de multiprocesadores tolerantes a fallos . En el sistema DIOGENES desarrollado por estos autores, las CPU de un sistema multiprocesador están dispuestas en una secuencia lógica correspondiente al lomo de un libro (aunque esta secuencia no necesariamente puede estar colocada a lo largo de una línea en el diseño físico 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 pilas : conectar uno de los procesadores al inicio 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 al que está en la parte inferior del paquete y baja todos los demás. Debido a este comportamiento de la pila, un solo paquete puede manejar un conjunto de enlaces de comunicaciones que forman los bordes de una sola página en la incrustación de un libro. Al organizar los enlaces de esta manera, se puede implementar una amplia variedad de topologías de red diferentes, independientemente de qué procesadores hayan resultado defectuosos, siempre que queden suficientes procesadores no defectuosos para implementar la red. Las topologías de red que este sistema puede implementar son exactamente aquellas que tienen un espesor de libro como máximo igual al número de paquetes que se han puesto a disposición. [40] La incrustación de libros también se puede utilizar para modelar la ubicación de los cables que conectan componentes VLSI en las capas de un circuito. [50]
Otra aplicación citada por Chung, Leighton y Rosenberg (1987) se refiere a la clasificación de permutaciones mediante pilas . Un resultado influyente de Donald Knuth (1968) demostró que un sistema que procesa un flujo de datos empujando los elementos entrantes a una pila y luego, en momentos elegidos apropiadamente, sacándolos de la pila a un flujo de salida, puede ordenar los datos si y sólo si. su orden inicial se describe mediante una permutación que evita el patrón de permutación 231. [51] Desde entonces, se ha trabajado mucho en problemas similares de clasificación de flujos de datos mediante 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) a un flujo de salida. Como Chung et al. Observe que una permutación dada puede ordenarse mediante este sistema si y sólo si un determinado gráfico, derivado de la permutación, tiene un libro incrustado con los vértices en un cierto orden fijo a lo largo del lomo y con un número de páginas que es como máximo igual. al número de pilas. [40]
Como describió Kainen (1990), se puede utilizar la incorporación de un libro para describir las fases de una señal de tráfico en una intersección controlada. En una intersección, los carriles de tráfico entrante y saliente (incluidos los extremos de los cruces peatonales y carriles para bicicletas, así como los carriles para vehículos motorizados) pueden representarse como los vértices de un gráfico, colocado en el lomo de un libro incrustado en el sentido de las agujas del reloj. orden alrededor del cruce. Los caminos a través de la intersección tomados por el tráfico para llegar de un carril entrante a un carril saliente pueden representarse como los bordes de un gráfico no dirigido. Por ejemplo, este gráfico podría tener un borde desde un carril de tráfico entrante a uno saliente que pertenecen al mismo segmento de la carretera, lo que representa un giro en U desde ese segmento hacia ese segmento, solo si se permiten giros en U en el unión. Para un subconjunto dado de estos bordes, el subconjunto representa una colección de caminos que pueden atravesarse sin interferencia entre sí si y sólo si el subconjunto no incluye ningún par de bordes que se cruzarían si los dos bordes se colocaran en un solo Página de un libro incrustado. Por lo tanto, la inclusión de este gráfico en un libro describe una partición de los caminos en subconjuntos que no interfieren, y el grosor del libro de este gráfico (con su inclusión fija en el lomo) proporciona el número mínimo de fases distintas necesarias para un programa de señalización que incluya todas las rutas de tráfico posibles a través del cruce. [52]
La incrustación 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 el dibujo de gráficos , los diagramas de arco [53] y los diseños circulares, [54] pueden verse como incrustaciones de libros, y la incrustación de libros también se ha aplicado en la construcción de diseños agrupados, [45] incrustaciones simultáneas, [55 ] y dibujos de gráficos tridimensionales. [56]
Un diagrama de arco [53] o incrustación lineal [43] coloca los vértices de un gráfico a lo largo de una línea y dibuja los bordes del gráfico como semicírculos por encima o por debajo de esta línea, a veces también permite dibujar bordes en segmentos de la línea. Este estilo de dibujo corresponde a un libro incrustado con una página (si todos los semicírculos están por encima de la línea) o dos páginas (si se utilizan ambos lados de la línea), y se introdujo originalmente como una forma de estudiar los números cruzados de los gráficos. [57] [58] Los gráficos planos que no tienen incrustaciones de libros de dos páginas también se pueden dibujar de manera similar, permitiendo que sus bordes se representen mediante múltiples semicírculos por encima y por debajo de la línea. Tal dibujo no es una incrustación de libro según la definición habitual, sino que se le ha llamado incrustación de libro topológico . [59] Para cada gráfico plano, siempre es posible encontrar una incrustación en la que cada borde cruce la columna vertebral como máximo una vez. [60]
En otro estilo de dibujo, el diseño circular , los vértices de un gráfico se colocan en un círculo y los bordes se dibujan dentro o fuera del círculo. [54] Nuevamente, una ubicación de los bordes dentro del círculo (por ejemplo, como segmentos de línea recta) corresponde a un dibujo de un libro de una página, mientras que una ubicación tanto dentro como fuera del círculo corresponde a un dibujo de un libro de dos páginas. [61]
Para dibujos de una página de cualquier estilo, es importante mantener pequeño el número de cruces como una forma de reducir el desorden visual del dibujo. Minimizar el número de cruces es NP-completo , [43] pero puede aproximarse con una relación de aproximación de O (log 2 n ) donde n es el número de vértices. [62] Minimizar el número de cruce de una o dos páginas es manejable con parámetros fijos cuando se parametriza por el número ciclomático del gráfico dado, o mediante una combinación del número de cruce y el ancho del árbol del gráfico. [63] [64] También se han ideado métodos heurísticos para reducir la complejidad del cruce, basados, por ejemplo, en un cuidadoso orden de inserción de vértices y en la optimización local . [54]
Las incrustaciones de libros de dos páginas con una partición fija de los bordes en páginas pueden interpretarse como una forma de planaridad agrupada , en la que el gráfico dado debe dibujarse de tal manera que partes del gráfico (los dos subconjuntos de bordes) se coloquen. en el dibujo de una manera que refleje su agrupación. [45] La incrustación de libros de dos páginas también se ha utilizado para encontrar incrustaciones simultáneas de gráficos, en las que se dan dos gráficos en el mismo conjunto de vértices y se debe encontrar una ubicación para los vértices en la que ambos gráficos se dibujen planamente con bordes rectos. [55]
También se han utilizado incrustaciones de libros con más de dos páginas para construir dibujos tridimensionales de gráficos. En particular, Wood (2002) utilizó una construcción para incrustaciones de libros que mantiene bajo el grado de cada vértice dentro de cada página, como parte de un método para incrustar gráficos en una cuadrícula tridimensional de bajo volumen. [56]
En el estudio de cómo se pliegan las moléculas de ARN para formar su estructura, la forma estándar de estructura secundaria del ácido nucleico se puede describir esquemáticamente como una cadena de bases (la secuencia de ARN en sí), dibujada a lo largo de una línea, junto con una colección de arcos sobre la misma. Línea que describe los pares de bases 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, la incrustación de un libro de una página. Sin embargo, no todos los pliegues del ARN se comportan de esta forma sencilla. Haslinger y Stadler (1999) han propuesto una denominada "estructura bi-secundaria" para ciertos pseudonudos de ARN que toma la forma de un libro de dos páginas incrustado: la secuencia de ARN se dibuja nuevamente a lo largo de una línea, pero los pares de bases se dibujan como arcos tanto por encima como por debajo de esta línea. Para formar una estructura bisecundaria, un grafo debe tener como máximo tres grados: cada base sólo puede participar en un arco del diagrama, además de los dos enlaces con sus vecinos en la secuencia de bases. Las ventajas de esta formulación incluyen el hecho de que excluye estructuras que en realidad están anudadas en el espacio y que coincide con la mayoría de los pseudonudos de ARN conocidos. [7]
Debido a que el orden de las espinas se conoce de antemano para esta aplicación, probar la existencia de una estructura bisecundaria para un par de bases determinado es sencillo. El problema de asignar aristas a las dos páginas de forma compatible se puede formular como un caso de 2-satisfacibilidad o como un problema de probar la bipartición del gráfico circular cuyos vértices son los pares de bases y cuyas aristas describen cruces entre pares de bases. [7] Alternativamente y más eficientemente, como muestran Haslinger y Stadler (1999), existe una estructura bisecundaria si y sólo si el diagrama gráfico de la entrada (un gráfico formado conectando las bases en un ciclo en su orden de secuencia y sumando los pares de bases dados como aristas) es un gráfico plano . [7] Esta caracterización permite reconocer estructuras bi-secundarias en tiempo lineal como un caso de prueba de planaridad .
Blin et al. (2007) utilizaron la conexión entre estructuras secundarias e incrustaciones de libros como parte de una prueba de la dureza NP de ciertos problemas en la comparación de estructuras secundarias de ARN. [65] Y si una estructura de ARN es terciaria en lugar de bi-secundaria (es decir, si requiere más de dos páginas en su diagrama), entonces determinar el número de página es nuevamente NP-difícil. [66]
Pavan, Tewari y Vinodchandran (2012) utilizaron la incorporación de libros para estudiar la teoría de la complejidad computacional del problema de alcanzabilidad en gráficos dirigidos . Como han observado, la accesibilidad de gráficos dirigidos de dos páginas se puede resolver en un espacio logarítmico inequívoco (el análogo, para la complejidad del espacio logarítmico , de la clase UP de problemas de tiempo polinomial inequívocos). Sin embargo, la accesibilidad de gráficos dirigidos de tres páginas requiere todo el poder del espacio logarítmico no determinista . Por lo tanto, las incrustaciones de libros parecen íntimamente conectadas con la distinción entre estas dos clases de complejidad. [67]
La existencia de gráficos de expansión con número de página constante [36] es el paso clave para demostrar que no existe una simulación en tiempo subcuadrático de máquinas de Turing no deterministas de dos cintas mediante máquinas de Turing no deterministas de una cinta. [68]
McKenzie y Overbay (2010) estudian las aplicaciones del espesor de libros en álgebra abstracta , utilizando gráficas definidas a partir de los divisores cero de un anillo local finito haciendo un vértice para cada divisor cero y una arista para cada par de valores cuyo producto es cero. [69]
En una secuencia de varios artículos, Dynnikov ha estudiado las incrustaciones topológicas de nudos y enlaces en libros , mostrando que estas incrustaciones 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 las incrustaciones. [70] [71]
