Embebido en libro

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.

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 K_n 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 ${\displaystyle O({\sqrt {n}})}$.^[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]

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 ${\displaystyle O({\sqrt {m}})}$,^[29] y los grafos de genus g tienen un grosor de libro de ${\displaystyle O({\sqrt {g}})}$.^[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 K_2,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 ${\displaystyle O({\sqrt {n}})}$ 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]

Encontrar el grosor del libro de un grafo es un problema de dificultad NP. Esto se deriva del hecho de que encontrar ciclos hamiltonianos en grafos planos máximos es una tarea NP-completa. 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 una tarea NP-completa 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 un embebido, entonces se puede encontrar un embebido de dos páginas (si existe) en tiempo lineal, como una instancia de prueba de planaridad para un grafo formado al aumentar el grafo dado con un ciclo que conecta los vértices según su orden en el lomo.^[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 tiempo lineal, 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 un embebido con el mínimo número posible de páginas sigue siendo de dificultad NP, a través de una equivalencia al problema de coloreado de grafos circulares, los grafos de intersección de las cuerdas de una circunferencia. Dado un grafo G con un lomo fijo 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 óptimo en un libro. 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 en libro, se deduce que el embebido óptim en libro 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 tiempo lineal mediante un algoritmo basado en un árbol SPQR.^[44][45] Sin embargo, es un problema NP-completo encontrar un embebido de 2 páginas cuando no se conoce el orden del lomo ni la partición de los vínculos. Encontrar el número de cruce del libro de un grafo también es NP-difícil, debido a la NP-complejidad 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 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 patrón es un subgrafo inducido del grafo más grande o si posee un homomorfismo con respecto al 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 manejable de parámetros fijos.^[48]

Bekos, Kaufmann y Zielke (2015) describió un sistema para encontrar embebidos en libro óptimos transformando el problema en una instancia de satisfacibilidad booleana y aplicando un solucionador SAT al problema resultante. Afirmó que su sistema es capaz de encontrar un embebido óptimo para grafos planos de 400 vértices en aproximadamente 20 minutos.^[34]

Una de las principales motivaciones para estudiar el embebido en 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 multiprocesamiento tolerante a fallos. En el sistema DIOGENES desarrollado por estos autores, la 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 diseño físico del 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 de datos: 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 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 los enlaces de esta manera, se puede desarrollar una amplia variedad de diferentes topologías de red, independientemente de qué procesadores hayan fallado, siempre que queden suficientes procesadores sin fallos para hacer funcionar la red. Las topologías de red que puede valerse de 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]

Otra aplicación citada por Chung, Leighton y Rosenberg (1987) se refiere a la clasificación de permutaciones utilizando pilas de datos.

Un resultado influyente de txt, mostró que un sistema que procesa un flujo de datos empujando elementos entrantes y luego, en los momentos elegidos apropiadamente, sacarlos de la pila a un flujo de salida puede ordenar los datos si y solo si su orden inicial es descrito por una permutación que evita el patrón de permutación 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. observaron, 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]

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 embebido en libro dispuesto en sentido horario según su 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 cruce de carreteras. Para un subconjunto dado de estos vínculos, el subconjunto representa una colección de caminos que se pueden recorrer sin interferencias entre sí, si y solo si el subconjunto no incluye ningún par de vínculos que se cruzasen si los dos vínculos se colocaran en una sola página de un libro de embebido. Por lo tanto, el embebido en libro de este grafo describe una partición de las rutas en subconjuntos que no se interfieren entre sí, y el grosor del libro de este grafo (con su embebido fijado 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]

El embebido en libro 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, los diagramas de arcos^[52] y los diseños circulares,^[53] se pueden ver como embebidos en libro, configuración que también se ha aplicado en la construcción de diseños agrupados,^[44] embebidos simultáneos^[54] y dibujos de grafos tridimensionales.^[55]

Un diagrama de arcos^[52] o embebido lineal^[42] coloca los vértices de un grafo en una recta y dibuja los vínculos del grafo como semicírculos por encima o por debajo de esta línea, y a veces también se permite dibujar vínculos en segmentos sobre la propia línea recta. Este estilo de dibujo corresponde a un embebido en libro con una página (si todos los semicírculos están situados por encima de la recta) o dos páginas (si se usan ambos lados de la recta), y se introdujo originalmente como una forma de estudiar los números de cruces 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 recta. Tal dibujo no es un embebido de libro según la definición habitual, pero se ha denominado embebido de libro topológico.^[58] Para cada grafo plano, siempre es posible encontrar un embebido en el que cada vínculo cruce la recta donde se sitúan los vértices como máximo una vez.^[59]

En otro estilo de dibujo, el diseño circular, los vértices de un grafo se colocan en una circunferencia y los vínculos se dibujan dentro o fuera de ella.^[53] Una vez más, la ubicación de los vínculos dentro de la circunferencia (por ejemplo, como segmentos de línea recta) corresponde al dibujo de un libro de una página, mientras que la ubicación de vínculos tanto dentro como fuera de la circunferencia 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 un problema NP-completo,^[42] pero puede aproximarse con una relación de aproximación de O(log² n) donde n es el número de vértices.^[61] Minimizar el número de cruces de una o dos páginas es un problema de complejidad parametrizada a partir del número ciclomático del grafo dado, o mediante una combinación del número de cruce y el ancho de árbol del grafo.^[62][63] También se han ideado métodos heurísticos para reducir la complejidad de los cruces, basados por ejemplo en un orden de inserción de vértices cuidadoso y en optimización local.^[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 planaridad agrupada, 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 embebidos simultáneos 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 grado de cada vértice dentro de cada página, como parte de un método para embeber grafos en una cuadrícula tridimensional de bajo volumen.^[55]

En el estudio de cómo las moléculas de ácido ribonucleico (ARN) se pliegan para formar su estructura, la forma estándar de estructura secundaria de ácido nucleico 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 describen 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, 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 pseudonudos de ARN que toman la forma de un libro de dos páginas embebido: la secuencia de ARN se dibuja nuevamente en una línea recta, pero los pares de bases se dibujan como arcos tanto arriba como abajo de 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 coinciden con la mayoría de los pseudonudos de ARN conocidos.^[7]

Debido a que el orden del lomo 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-satisfacibilidad o como un problema de prueba de bipartibilidad de un grafo circular 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 muestraHaslinger 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 prueba de planaridad.Blin et al. (2007) usó la conexión entre las estructuras secundarias y los embebidos en libro como parte de una prueba de la dificultad 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]

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]

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]