Incrustación de libros

Disposición de gráficos en múltiples semiplanos

Incorporación en un libro de tres páginas del gráfico completo K _5. Debido a que no es un gráfico planar , no es posible incorporar este gráfico sin cruces en menos páginas, por lo que su grosor es tres.

En teoría de grafos , una incrustación de libro es una generalización de la incrustación plana de un grafo 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 grafo se encuentren en esta línea límite, llamada lomo , y se requiere que los bordes permanezcan dentro de un solo semiplano. El grosor del libro de un grafo es el número más pequeño posible de semiplanos para cualquier incrustación de libro del grafo. El grosor del libro también se llama número de página , número de pila o grosor exterior fijo . Las incrustaciones de libros también se han utilizado para definir varios otros invariantes de grafos, incluidos el ancho de página y el número de cruce del libro.

Cada grafo con n vértices tiene un grosor de libro como máximo , y esta fórmula da el grosor de libro exacto para grafos completos . Los grafos con un grosor de libro uno son los grafos planos exteriores . Los grafos con un grosor de libro como máximo dos son los grafos subhamiltonianos , que siempre son planos ; de manera más general, cada grafo plano tiene un grosor de libro como máximo cuatro. Es NP-difícil determinar el grosor de libro exacto de un grafo dado, con o sin conocer un orden fijo de vértices a lo largo del lomo del libro. Probar la existencia de una incrustación de libro de tres páginas de un grafo, 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 si se puede resolver en tiempo polinomial ni si es NP-difícil. ${\displaystyle \lceil n/2\rceil }$

Una de las motivaciones originales para estudiar las incrustaciones de libros involucraba aplicaciones en el diseño VLSI , en el que los vértices de una incrustación de libro 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 origen-destino. Se puede utilizar una incrustación de libro de este gráfico 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 señal. En problemas de bioinformática que involucran la estructura de plegamiento del ARN , las incrustaciones de libro de una sola página representan formas clásicas de la estructura secundaria del ácido nucleico , y las incrustaciones de libro de dos páginas representan pseudonudos . Otras aplicaciones de las incrustaciones de libro incluyen el álgebra abstracta y la teoría de nudos .

Historia

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ó las incrustaciones de grafos en libros. Las incrustaciones que estudió utilizaron la misma definición que las incrustaciones de grafos en cualquier otro espacio topológico: los vértices se representan por puntos distintos, las aristas se representan por curvas y la única forma en que dos aristas 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 incrustación más restringido que se utilizó en la mayoría de las investigaciones posteriores. En su formulación, los vértices del grafo deben ubicarse a lo largo del lomo del libro y cada borde debe estar en una sola página. ^{[3] [4]} Entre los hitos importantes en el desarrollo posterior de las incrustaciones de libros se incluyen la prueba de Mihalis Yannakakis a fines de la década de 1980 de que los grafos planares tienen un grosor de libro de cuatro como máximo, ^{[5] [6]} y el descubrimiento a fines de la década de 1990 de conexiones estrechas entre las incrustaciones de libros y la bioinformática . ^[7]

Definiciones

El gráfico de utilidad K _3,3 no tiene incrustación 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 en el libro de 2 páginas es 1.

Esta incrustación de una página del gráfico de diamante tiene un ancho de página de 3, porque el rayo amarillo cruza tres bordes.

Un libro es un tipo particular de espacio topológico , también llamado abanico de semiplanos. ^{[1] [8]} Consiste en una sola línea ℓ , llamada lomo o parte posterior del libro, junto con una colección de uno o más semiplanos , llamados páginas u hojas del libro, ^[9] cada uno teniendo el lomo como su límite. Los libros con un número finito de páginas se pueden incrustar en el espacio tridimensional, por ejemplo, eligiendo ℓ como el eje z de un sistema de coordenadas cartesianas y eligiendo las páginas como los k semiplanos cuyo ángulo diedro con respecto al plano xz es un múltiplo entero de 2 π / k . ^[10]

Un dibujo de un 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 dibuja como un punto en el lomo de B , y cada borde de G se dibuja como una curva que se encuentra dentro de una sola página de B. El número de cruces de k páginas de G es el número mínimo de cruces en un dibujo de libro de k páginas. ^[11]

Una incrustación de libro de G sobre B es un dibujo de libro que forma una incrustación de gráfico de G sobre B. Es decir, es un dibujo de libro de G sobre B que no tiene ningún cruce de aristas. Todo grafo finito tiene una incrustación de libro sobre un libro con una cantidad suficientemente grande de páginas. Por ejemplo, siempre es posible incrustar cada arista del grafo en su propia página separada. El grosor del libro , el número de página o el número de pila de G es la cantidad mínima de páginas requeridas para una incrustación de libro de  G. Otro parámetro que mide la calidad de una incrustación de libro, más allá de su cantidad de páginas, es su ancho de página . Este se define de manera análoga a ancho de corte como la cantidad máxima de aristas 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 intersecan 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 Atneosen ya observó, si los bordes pueden pasar de una página a otra a través del lomo del libro, entonces cada grafo puede ser incrustado en un libro de tres páginas. ^{[15] [2] [16]} Para una incrustación topológica de un libro de tres páginas en la que se permiten los cruces de lomo, cada grafo puede ser incrustado con, como máximo, un número logarítmico de cruces de lomo por borde, ^[15] y algunos grafos necesitan esta cantidad de cruces de lomo. ^[17]

Gráficos específicos

Como se muestra en la primera figura, el grosor del libro del grafo completo K ₅ es tres: como grafo no plano, su grosor es mayor que dos, pero existe una incrustación de libro con tres páginas. En términos más generales, el grosor del libro de cada grafo completo con n ≥ 4 vértices es exactamente . Este resultado también proporciona un límite superior para el grosor máximo posible del libro de cualquier grafo de n vértices. ^[10] ${\displaystyle \lceil n/2\rceil }$

El número de cruce de dos páginas del gráfico completo K _n es

${\displaystyle {\frac {1}{4}}{\biggl \lfloor }{\frac {n}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {n-1}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {n-2}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {n-3}{2}}{\biggr \rfloor },}$

Coincidiendo con una conjetura aún no demostrada de Anthony Hill sobre cuál debería ser el número de cruces sin restricciones 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 grosor del libro del grafo bipartito completo K _{a , b} es como máximo min( a , b ) . Para construir un dibujo con este grosor, para cada vértice del lado más pequeño de la bipartición, se pueden colocar las aristas 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 del grafo están muy desequilibrados, con b > a ( a − 1) , el grosor del libro de K _{a , b} es exactamente a . ^{[10] [19]}

Para el grafo de Turán T ( kr , r ) (un grafo multipartito completo K _{k , k ,...} formado a partir de r conjuntos independientes de k vértices por conjunto independiente, con una arista entre cada dos vértices de diferentes conjuntos independientes) el espesor del libro t está intercalado entre

${\displaystyle \left\lceil {\frac {k(r-1)}{2}}\right\rceil \leq t\leq \left\lceil {\frac {kr}{2}}\right\rceil }$

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

${\displaystyle t\leq (r-1)\left\lceil {\frac {k}{2}}\right\rceil +\left\lceil {\frac {k}{4}}\right\rceil .}$^{[10] [20]}

El grosor del libro de los grafos binarios de Bruijn , los grafos de intercambio aleatorio y los ciclos cúbicos conexos (cuando estos grafos son lo suficientemente grandes como para ser no planos) es exactamente tres. ^[21]

Propiedades

Planaridad y planaridad exterior

El gráfico de Goldner-Harary , un gráfico planar con un grosor de libro de tres

El grosor del libro de un grafo G dado es como máximo uno si y solo si G es un grafo exterior-planar . Un grafo exterior-planar es un grafo que tiene una incrustación plana en la que todos los vértices pertenecen a la cara exterior de la incrustación. Para un grafo de este tipo, colocar los vértices en el mismo orden a lo largo del lomo en el que aparecen en la cara exterior proporciona una incrustación 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 la incrustación de libro). Por el contrario, una incrustación de libro de una página es automáticamente una incrustación exterior-planar. Porque, si un grafo está incrustado en una sola página, y otro semiplano se une al lomo para extender su página a un plano completo, entonces la cara exterior de la incrustación incluye todo el semiplano añadido, y todos los vértices se encuentran en esta cara exterior. ^{[10] [12]}

Cada incrustación de libro de dos páginas es un caso especial de incrustación planar, 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 planar . Más precisamente, el grosor de libro de un grafo G es como máximo dos si y solo si G es un subgrafo de un grafo planar que tiene un ciclo hamiltoniano . ^[10] Si a un grafo se le da una incrustación de dos páginas, se puede aumentar a un grafo hamiltoniano planar agregando (en cualquier página) aristas adicionales entre dos vértices consecutivos a lo largo del lomo que no sean ya adyacentes, y entre el primer y el último vértice del lomo. El grafo de Goldner-Harary proporciona un ejemplo de un grafo planar que no tiene grosor de libro dos: es un grafo planar maximalista , por lo que no es posible agregarle aristas mientras se preserva 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 grafos planares cuyo grado máximo es como máximo cuatro tienen un grosor de libro como máximo dos. ^[22] Los 3-árboles planares tienen un grosor de libro como máximo tres. ^[23] De manera más general, todos los grafos planares tienen un grosor de libro cuatro. ^{[5] [6] [24]} Mihalis Yannakakis afirmó en 1986 ^[6] que existen algunos grafos planares 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 grafos planares con un ancho de árbol de 4 que requieren cuatro páginas en cualquier incrustación de libro.

Comportamiento en subdivisiones

El grosor del libro del gráfico de diamante aumenta después de la subdivisión del borde.

Subdividir cada arista de un grafo en caminos de dos aristas, agregando nuevos vértices dentro de cada arista, a veces puede aumentar su grosor de libro. Por ejemplo, el grafo de diamante tiene un grosor de libro uno (es exteriormente plano) pero su subdivisión tiene un grosor de libro dos (es plano y subhamiltoniano pero no exteriormente plano). Sin embargo, este proceso de subdivisión también puede a veces reducir significativamente el grosor de libro del grafo subdividido. Por ejemplo, el grosor de libro del grafo completo K _n es proporcional a su número de vértices, pero subdividir cada una de sus aristas en un camino de dos aristas produce una subdivisión cuyo grosor de libro es mucho menor, solo . ^[25] A pesar de la existencia de ejemplos como este, Blankenship y Oporowski (1999) conjeturaron que el grosor de libro de una subdivisión no puede ser mucho menor que el del grafo original. En concreto, conjeturaron que existe una función f tal que, para cada grafo G y para el grafo H formado al reemplazar cada arista en G por un camino de dos aristas, 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 grafos formados por productos cartesianos de estrellas y teselas triangulares tienen un espesor de libro ilimitado, pero subdividir sus aristas en caminos de seis aristas reduce su espesor de libro a tres. ^[26] ${\displaystyle O({\sqrt {n}})}$

Relación con otros invariantes gráficos

El grosor del libro está relacionado con el grosor , el número de grafos planos necesarios para cubrir las aristas del grafo dado. Un grafo G tiene grosor θ si se puede dibujar en el plano, y sus aristas coloreadas con θ colores, de tal manera que las aristas del mismo color no se crucen. Análogamente, un grafo G tiene grosor de libro θ si se puede dibujar en un semiplano , con sus vértices en el límite del semiplano, con sus aristas coloreadas con θ colores sin cruce entre dos aristas del mismo color. En esta formulación del grosor del libro, los colores de las aristas corresponden a las páginas del libro incrustado. Sin embargo, el grosor 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 grosor dos. ^[25]

Los grafos de ancho de árbol k tienen un grosor de libro como máximo k + 1 ^{[27] [28]} y este límite es estricto para k > 2 . ^[27] Los grafos con m aristas tienen un grosor de libro , ^[29] y los grafos de género g tienen un grosor de libro . ^[30] De manera más general, se ha afirmado que cada familia de grafos cerrada por menores tiene un grosor de libro acotado. ^{[31] [32]} Sin embargo, la prueba de esta afirmación se basa en una afirmación previa de que los grafos incrustados en superficies no orientables tienen un grosor de libro acotado, para la que no se ha proporcionado una prueba detallada. ^[33] Los grafos 1-planares , que no están cerrados bajo menores, ^[31] tienen un grosor de libro acotado, ^[34] pero algunos grafos 1-planares que incluyen K _2,2,2,2 tienen un grosor de libro de al menos cuatro. ^[35] ${\displaystyle O({\sqrt {m}})}$ ${\displaystyle O({\sqrt {g}})}$

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

Como los grafos de grosor dos son grafos planares, obedecen al teorema del separador planar : tienen separadores, subconjuntos de vértices cuya eliminación divide el grafo en partes con un máximo de 2 n /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 tres que no tienen separadores de tamaño sublineal. ^[37] ${\displaystyle O({\sqrt {n}})}$

Los bordes dentro de una sola página de una incrustación de libro se comportan de alguna manera como una estructura de datos de pila . Esto se puede formalizar considerando una secuencia arbitraria de operaciones de inserción y extracción en una pila, y formando un gráfico en el que las operaciones de pila corresponden a los vértices del gráfico, colocados en orden de secuencia a lo largo del lomo de una incrustación de libro. Luego, si uno dibuja un borde desde cada operación de extracción que extrae un objeto x de la pila, hasta la operación de inserción anterior que empujó x , el gráfico resultante tendrá automáticamente una incrustación de una página. Por esta razón, el número de página de un gráfico también se ha llamado su número de pila . De la misma manera, uno puede considerar una secuencia arbitraria de operaciones de encolar y desencolar de una estructura de datos de cola , y formar un gráfico que tenga estas operaciones como sus vértices, colocados en orden en el lomo de una sola página, con un borde entre cada operación de encolar y la desencolar correspondiente. Luego, en este gráfico, cada dos bordes cruzarán o cubrirán intervalos disjuntos en el lomo. 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 encuentre en el lomo, cada arista se encuentre en una sola página y cada dos aristas de la misma página se crucen o cubran intervalos disjuntos en el lomo. El número mínimo de páginas necesarias para una incrustación en cola de un gráfico se denomina su número de cola . ^{[31] [38] [39]}

Complejidad computacional

Un gráfico circular , el gráfico de intersección de las cuerdas de un círculo. Para las incrustaciones de libros con un orden de vértices fijo, encontrar el grosor del libro es equivalente a colorear un gráfico circular derivado.

Encontrar el grosor del libro de un grafo es NP-difícil . Esto se deduce del hecho de que encontrar ciclos hamiltonianos en grafos planos maximalistas es NP-completo . ^[40] En un grafo plano maximalista, el grosor del libro es dos si y solo si existe un ciclo hamiltoniano. Por lo tanto, también es NP-completo comprobar si el grosor del libro de un grafo plano maximalista dado es dos. ^[41]

Si un orden de los vértices de un grafo a lo largo de la columna vertebral de una incrustación es fijo, entonces una incrustación de dos páginas (si existe) se puede encontrar 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 en su orden de columna vertebral. ^[7] Unger (1992) afirmó que encontrar incrustaciones de tres páginas con un orden de columna vertebral fijo también se puede realizar en tiempo polinomial , aunque su redacción de este resultado omite muchos detalles. ^[42] Sin embargo, para grafos 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-duro, a través de una equivalencia con el problema NP-duro de colorear grafos circulares , los grafos de intersección de cuerdas de un círculo . Dado un grafo G con un ordenamiento fijo de lomo 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 . Entonces se puede formar un grafo circular que tiene las cuerdas de este diagrama como vértices y pares de cuerdas que se cruzan como bordes. Una coloración del grafo circular representa una partición de los bordes 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 incrustación óptima de libros. Dado que la coloración de grafos circulares con cuatro o más colores es NP-hard, y dado que cualquier grafo 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 libros también es NP-hard. ^{[43] [44] [45]} Para un ordenamiento fijo de vértices en el lomo de un dibujo de libro de dos páginas, también es NP-hard minimizar el número de cruces cuando este número es distinto de cero. ^[44]

Si se desconoce el orden del lomo pero se da 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 . ^{[46] [47]} Sin embargo, es NP-completo encontrar una incrustación de 2 páginas cuando no se conoce ni el orden del lomo ni la partición de los bordes. Encontrar el número de cruce de libros 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 de isomorfismo de subgrafos , de encontrar si un grafo patrón de tamaño acotado existe como un subgrafo de un grafo mayor, se puede resolver en tiempo lineal cuando el grafo mayor tiene un grosor de libro acotado. Lo mismo es cierto para detectar si el grafo patrón es un subgrafo inducido del grafo mayor, o si tiene un homomorfismo de grafos con el grafo mayor. ^{[48] [49]} 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 con parámetros fijos . ^[50]

Bekos, Kaufmann y Zielke (2015) describen un sistema para encontrar incrustaciones óptimas de libros transformando el problema en una instancia del problema de satisfacibilidad booleana y aplicando un solucionador SAT al problema resultante. Afirman que su sistema es capaz de encontrar una incrustación óptima para gráficos planos maximalistas de 400 vértices en aproximadamente 20 minutos. ^[35]

Aplicaciones

Multiprocesamiento tolerante a fallos

Una de las principales motivaciones para estudiar la incrustació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 que corresponde al lomo de un libro (aunque esta secuencia puede no estar necesariamente 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 están agrupados 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 comunicación empuja todos los enlaces anteriores hacia arriba en el paquete, y conectar otro procesador al final de un enlace de comunicación lo conecta al que está en la parte inferior del paquete y hace que todos los demás se ubiquen hacia abajo. Debido a este comportamiento de pila, un solo paquete puede manejar un conjunto de enlaces de comunicación que forman los bordes de una sola página en una incrustación de libro. Al organizar los enlaces de esta manera, se puede implementar una amplia variedad de topologías de red diferentes, independientemente de qué procesadores se hayan vuelto defectuosos, siempre que queden suficientes procesadores que no presenten fallas para implementar la red. Las topologías de red que se pueden implementar con 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. ^[41] La incrustación de libros también se puede utilizar para modelar la colocación de cables que conectan componentes VLSI en las capas de un circuito. ^[51]

Ordenamiento por pila

Otra aplicación citada por Chung, Leighton y Rosenberg (1987) se refiere a la ordenación de permutaciones utilizando pilas . Un resultado influyente de Donald Knuth  (1968) mostró que un sistema que procesa un flujo de datos empujando los elementos entrantes hacia una pila y luego, en momentos elegidos apropiadamente, sacándolos de la pila hacia un flujo de salida puede ordenar los datos si y solo si su orden inicial está descrito por una permutación que evita el patrón de permutación 231. ^[52] Desde entonces, ha habido mucho trabajo sobre problemas similares de ordenació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 empujarse hacia una de varias pilas. Luego, una vez que todos los datos han sido empujados de esta manera, los elementos se extraen de estas pilas (en un orden apropiado) hacia un flujo de salida. Como Chung et al. Obsérvese que una permutación dada puede ser ordenada por este sistema si y sólo si un cierto gráfico, derivado de la permutación, tiene una incrustación de libro 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. ^[41]

Control de tráfico

Una intersección de tráfico. Los cuatro pares de carriles de entrada y salida, dos puntos de giro y cuatro cruces de peatones en las esquinas se pueden representar como un conjunto de 14 vértices en el lomo de un libro, con bordes que representan conexiones entre estos puntos.

Como describió Kainen (1990), una incrustación de libro puede utilizarse para describir las fases de un semáforo en una intersección controlada. En una intersección, los carriles de entrada y salida del tráfico (incluidos los extremos de los cruces peatonales y carriles para bicicletas, así como los carriles para vehículos de motor) pueden representarse como los vértices de un gráfico, colocados en el lomo de una incrustación de libro en su orden horario alrededor de la intersección. Los caminos que sigue el tráfico a través de la intersección para llegar desde un carril de entrada a un carril de salida pueden representarse como los bordes de un gráfico no dirigido. Por ejemplo, este gráfico puede tener un borde desde un carril de entrada a uno de salida que pertenezcan al mismo segmento de la carretera, lo que representa un giro en U desde ese segmento de vuelta a ese segmento, solo si se permiten los giros en U en la intersección. Para un subconjunto dado de estos bordes, el subconjunto representa una colección de caminos que pueden recorrerse todos sin interferencia entre sí si y solo si el subconjunto no incluye ningún par de bordes que se cruzarían si los dos bordes se colocaran en una sola página de una incrustación de libro. Por lo tanto, una incrustación de libro de este grafo describe una partición de los caminos en subconjuntos que no interfieren, y el grosor del libro de este grafo (con su incrustación fija en el lomo) proporciona el número mínimo de fases distintas necesarias para un programa de señalización que incluye todos los caminos de tráfico posibles a través de la unión. ^[53]

Dibujo gráfico

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

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 ^[54] y los diseños circulares ^[55] , se pueden considerar incrustaciones de libros, y la incrustación de libros también se ha aplicado en la construcción de diseños agrupados ^[46] , incrustaciones simultáneas ^[56] y dibujos de gráficos tridimensionales ^{[57] .}

Un diagrama de arco ^[54] o incrustación lineal ^[44] 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 permitiendo que los bordes se dibujen en segmentos de la línea. Este estilo de dibujo corresponde a una incrustación de libro 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 de cruce de gráficos. ^{[58] [59]} Los gráficos planares que no tienen incrustaciones de libro de dos páginas también se pueden dibujar de una manera similar, permitiendo que sus bordes se representen por múltiples semicírculos por encima y por debajo de la línea. Un dibujo de este tipo no es una incrustación de libro según la definición habitual, sino que se ha denominado incrustación de libro topológica . ^[60] Para cada gráfico planar, siempre es posible encontrar una incrustación de este tipo en la que cada borde cruza el lomo como máximo una vez. ^[61]

Disposición circular del grafo de Chvátal

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. ^[55] Nuevamente, una colocación de los bordes dentro del círculo (por ejemplo, como segmentos de línea recta) corresponde a un dibujo de libro de una página, mientras que una colocación tanto dentro como fuera del círculo corresponde a un dibujo de libro de dos páginas. ^[62]

Para dibujos de una página de cualquier estilo, es importante mantener el número de cruces pequeño como una forma de reducir el desorden visual del dibujo. Minimizar el número de cruces es NP-completo , ^[44] pero puede aproximarse con una razón de aproximación de O (log ²  n ) donde n es el número de vértices. ^[63] Minimizar el número de cruces de una página o de dos páginas es manejable con parámetros fijos cuando se parametriza por el número ciclomático del gráfico dado, o por una combinación del número de cruces y el ancho de árbol del gráfico. ^{[64] [65]} 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 la optimización local . ^[55]

Las incrustaciones de libros de dos páginas con una partición fija de los bordes en páginas se pueden interpretar como una forma de planaridad agrupada , en la que el gráfico dado debe dibujarse de tal manera que las partes del gráfico (los dos subconjuntos de bordes) se coloquen en el dibujo de una manera que refleje su agrupamiento. ^[46] 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 dos gráficos se dan en el mismo conjunto de vértices y uno debe encontrar una ubicación para los vértices en la que ambos gráficos se dibujan de manera plana con bordes rectos. ^[56]

Las incrustaciones de libros con más de dos páginas también se han utilizado 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. ^[57]

Plegamiento del ARN

Fragmento de telomerasa humana que muestra un pseudonudo . Si se extiende el fragmento en línea recta a lo largo del lomo de un libro, los pares de bases azules se pueden dibujar en dos subconjuntos que no se cruzan por encima y por debajo del lomo, lo que muestra que este pseudonudo forma una estructura bisecundaria.

En el estudio de cómo las moléculas de ARN se pliegan para formar su estructura, la forma estándar de la estructura secundaria de los ácidos nucleicos 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 por encima de la 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) se puede describir mediante una estructura más abstracta, una incrustación de un libro de una página. Sin embargo, no todos los pliegues de ARN se comportan de esta manera simple. Haslinger y Stadler (1999) han propuesto una denominada "estructura bisecundaria" para ciertos pseudonudos de ARN que adopta la forma de una incrustación de un libro de dos páginas: la secuencia de ARN se dibuja de nuevo 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 un grado máximo de tres como máximo: cada base solo puede participar en un arco del diagrama, además de los dos enlaces a sus vecinas en la secuencia de bases. Las ventajas de esta formulación incluyen el hecho de que excluye las 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 emparejamiento de bases dado es sencilla. El problema de asignar aristas a las dos páginas de una manera compatible se puede formular como una instancia de 2-satisfacibilidad o como un problema de prueba de la bipartididad del grafo circular cuyos vértices son los pares de bases y cuyas aristas describen cruces entre pares de bases. ^[7] De manera alternativa y más eficiente, como muestran Haslinger y Stadler (1999), existe una estructura bisecundaria si y solo si el grafo del diagrama de la entrada (un grafo formado conectando las bases en un ciclo en su orden de secuencia y agregando los pares de bases dados como aristas) es un grafo planar . ^[7] Esta caracterización permite que las estructuras bisecundarias se reconozcan en tiempo lineal como una instancia de prueba de planaridad .

Blin et al. (2007) utilizaron la conexión entre las estructuras secundarias y las incrustaciones de libros como parte de una prueba de la NP-dureza de ciertos problemas en la comparación de la estructura secundaria del ARN. ^[66] 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), entonces determinar el número de página es nuevamente NP-dureza. ^[67]

Teoría de la complejidad computacional

Pavan, Tewari y Vinodchandran (2012) utilizaron la incrustación de libros para estudiar la teoría de la complejidad computacional del problema de alcanzabilidad en grafos dirigidos . Como han observado, la alcanzabilidad para grafos dirigidos de dos páginas puede resolverse 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 alcanzabilidad para grafos dirigidos de tres páginas requiere toda la potencia del espacio logarítmico no determinista . Por lo tanto, las incrustaciones de libros parecen estar íntimamente conectadas con la distinción entre estas dos clases de complejidad. ^[68]

La existencia de gráficos expansores con número de página constante ^[37] 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 por parte de máquinas de Turing no deterministas de una cinta. ^[69]

Otras áreas de las matemáticas

McKenzie y Overbay (2010) estudian aplicaciones del grosor del libro en el álgebra abstracta , utilizando gráficos definidos a partir de los divisores de cero de un anillo local finito haciendo un vértice para cada divisor de cero y una arista para cada par de valores cuyo producto sea cero. ^[70]

En una secuencia de varios artículos, Dynnikov ha estudiado las incrustaciones topológicas de nudos y enlaces , 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. ^{[71] [72]}

Referencias

1. Persinger, CA (1966), "Subconjuntos de n -libros en E ³ ", Pacific Journal of Mathematics , 18 : 169–173, doi : 10.2140/pjm.1966.18.169 , MR  0195077.
2. Atneosen, Gail Adele (1968), Sobre la incrustabilidad de compacta en n-libros: propiedades intrínsecas y extrínsecas, tesis doctoral, Michigan State University , pág. 79, MR  2617705. Véase también Atneosen, Gail H. (1972), "Continuos unidimensionales de n hojas" (PDF) , Fundamenta Mathematicae , 74 (1): 43–45, doi : 10.4064/fm-74-1-43-45 , Señor  0293592.
3. Kainen, Paul C. (1974), "Algunos resultados recientes en teoría de grafos topológicos", en Bari, Ruth A.; Harary, Frank (eds.), Graphs and Combinatorics (Actas de la Conferencia Capital sobre teoría de grafos y combinatoria en la Universidad George Washington del 18 al 22 de junio de 1973) , Lecture Notes in Mathematics, vol. 406, págs. 76-108.
4. Ollmann, L. Taylor (1973), "Sobre los espesores de libro de varios grafos", en Hoffman, Frederick; Levow, Roy B.; Thomas, Robert SD (eds.), Proc. 4th Southeastern Conference on Combinatorics, Graph Theory and Computing , Congressus Numerantium, vol. VIII, p. 459.
5. Yannakakis, Mihalis (1989), "Incorporación de gráficos planares en cuatro páginas", Journal of Computer and System Sciences , 38 : 36–67, doi : 10.1016/0022-0000(89)90032-9
6. Yannakakis, Mihalis (1986), "Cuatro páginas son necesarias y suficientes para los gráficos planares", Actas del 18.º Simposio ACM sobre teoría de la computación (STOC '86) , pp. 104-108, doi :10.1145/12130.12141, ISBN 0-89791-193-8, Número de identificación del sujeto  5359519.
7. Haslinger, Christian; Stadler, Peter F. (1999), "Estructuras de ARN con pseudonudos: propiedades grafoteóricas, combinatorias y estadísticas", Bulletin of Mathematical Biology , 61 (3): 437–467, doi :10.1006/bulm.1998.0085, PMC 7197269 , PMID  17883226 .
8. Hales, TC (1997), "Empaquetamientos de esferas. II", Geometría discreta y computacional , 18 (2): 135–149, doi : 10.1007/PL00009312 , hdl : 2027.42/42419 , MR  1455511.
9. La terminología "lomo" y "páginas" es más habitual en los enfoques de teoría de grafos modernos sobre el tema. Para la terminología "espalda" y "hojas", véase Persinger (1966).
10. Bernhart, Frank R.; Kainen, Paul C. (1979), "El grosor de un grafo", Journal of Combinatorial Theory , Serie B, 27 (3): 320–331, doi : 10.1016/0095-8956(79)90021-2 , MR  0554297.
11. Shahrokhi, Farhad; Székely, László A.; Sykora, Ondrej; Vrťo, Imrich (1996), "El libro que cruza el número de un gráfico", Journal of Graph Theory , 21 (4): 413–424, doi :10.1002/(SICI)1097-0118(199604)21:4<413: :AID-JGT7>3.3.CO;2-5, SEÑOR  1377615.
12. Heath, Lenwood S. (1987), "Incorporación de gráficos planos exteriores en libros pequeños", SIAM Journal on Algebraic and Discrete Methods , 8 (2): 198–218, doi :10.1137/0608018, MR  0881181.
13. Stöhr, Elena (1988), "Una compensación entre el número de página y el ancho de página de las incrustaciones de gráficos en libros", Información y computación , 79 (2): 155–162, doi : 10.1016/0890-5401(88)90036-3 , MR  0968104.
14. Stöhr, Elena (1991), "El ancho de página de los grafos planos trivalentes", Discrete Mathematics , 89 (1): 43–49, doi : 10.1016/0012-365X(91)90398-L , MR  1108073.
15. Enomoto, Hikoe; Miyauchi, Miki Shimabara (1999), "Incorporación de gráficos en un libro de tres páginas con O ( M log N ) cruces de aristas sobre el lomo", SIAM Journal on Discrete Mathematics , 12 (3): 337–341, doi :10.1137/S0895480195280319, MR  1710241.
16. Blankenship, Robin; Oporowski, Bogdan (1999), Dibujo de subdivisiones de gráficos completos y bipartitos completos en libros , Informe técnico 1999-4, Departamento de Matemáticas, Universidad Estatal de Luisiana, CiteSeerX 10.1.1.36.4358 .
17. Enomoto, Hikoe; Miyauchi, Miki Shimabara; Ota, Katsuhiro (1999), "Límites inferiores para el número de cruces de aristas sobre el lomo en una incrustación topológica de un libro de un gráfico", Discrete Applied Mathematics , 92 (2–3): 149–155, doi : 10.1016/S0166-218X(99)00044-X , MR  1697548.
18. Ábrego, Bernardo M.; Aichholzer, Oswin; Fernández-Merchant, Silvia; Ramos, Pedro; Salazar, Gelasio (2012), "El número de cruce de 2 páginas de K _n (resumen extendido)", Actas del 28.º Simposio Anual sobre Geometría Computacional (SCG'12) , ACM, Nueva York, págs. 397–403, doi :10.1145/2261250.2261310, MR  3050657, S2CID  8344088.
19. Para obtener resultados adicionales sobre el grosor del libro de gráficos bipartitos completos, consulte Enomoto, Hikoe; Nakamigawa, Tomoki; Ota, Katsuhiro (1997), "Sobre el número de páginas de gráficos bipartitos completos", Journal of Combinatorial Theory , Serie B, 71 (1): 111–120, doi : 10.1006/jctb.1997.1773 , MR  1469870; de Klerk, Etienne; Pasechnik, Dmitrii V.; Salazar, Gelasio (2014), "Dibujos de libros de grafos bipartitos completos", Discrete Applied Mathematics , 167 : 80–93, arXiv : 1210.2918 , doi :10.1016/j.dam.2013.11.001, MR  3166108, S2CID  40920263.
20. Sperfeld, Konrad (2013), "Sobre el número de página de gráficos impares-partitos completos", Discrete Mathematics , 313 (17): 1689–1696, doi : 10.1016/j.disc.2013.04.028 , MR  3061004.
21. Hasunuma, Toru; Shibata, Yukio (1997), "Incorporación de redes de De Bruijn, Kautz y de intercambio aleatorio en libros", Discrete Applied Mathematics , 78 (1–3): 103–116, doi : 10.1016/S0166-218X(97)00009-7 , MR  1475820; Tanaka, Yuuki; Shibata, Yukio (2010), "Sobre el número de página de los ciclos conexos con cubos", Matemáticas en Ciencias de la Computación , 3 (1): 109–117, doi :10.1007/s11786-009-0012-y, MR  2596254, S2CID  11830437Véase también Obrenić, Bojana (1993), "Incorporación de gráficos de Bruijn y de intercambio aleatorio en cinco páginas", SIAM Journal on Discrete Mathematics , 6 (4): 642–654, doi :10.1137/0406049, MR  1241401.
22. Bekos, Michael A.; Gronemann, Martin; Raftopoulou, Chrysanthi N. (2014), "Incorporaciones de libros de dos páginas de grafos de 4 planos", Actas del 31.º Simposio sobre aspectos teóricos de la informática , Leibniz International Proceedings in Informatics (LIPIcs), vol. 25, págs. 137-148, arXiv : 1401.0684 , doi : 10.4230/LIPIcs.STACS.2014.137 , ISBN 9783939897651.
23. Heath, Lenny (1984), "Incorporación de gráficos planares en siete páginas", Actas del 25.º Simposio anual sobre fundamentos de la informática , pp. 74-83, doi :10.1109/SFCS.1984.715903, ISBN 0-8186-0591-X.
24. Bekos, Michael A.; Kaufmann, Micheal; Klute, Fabian; Pupyrev, Sergey; Raftopoulou, Chrysanthi; Ueckerdt, Torsten (2020), "Cuatro páginas son realmente necesarias para los gráficos planares", Journal of Computational Geomerty , 1 (11): 332–353, arXiv : 2004.07630.
25. Eppstein, David (2001), "Separación del espesor geométrico del espesor del libro", arXiv : math.CO/0109195{{cite arXiv}}: Mantenimiento de CS1: configuración anulada ( enlace ).
26. Dujmović, Vida ; Eppstein, David ; Hickingbotham, Robert; Morin, Pat ; Wood, David R. (agosto de 2021), "El número de pila no está limitado por el número de cola", Combinatorica , 42 (2): 151–164, arXiv : 2011.04195 , doi :10.1007/s00493-021-4585-7, S2CID  226281691
27. Dujmović, Vida ; Wood, David R. (2007), "Ancho de árbol de gráficos y parámetros de espesor geométrico", Geometría discreta y computacional , 37 (4): 641–670, arXiv : math/0503553 , doi :10.1007/s00454-007-1318-7, S2CID  9141367.
28. Ganley, Joseph L.; Heath, Lenwood S. (2001), "El número de página de los árboles k es O ( k ) ", Discrete Applied Mathematics , 109 (3): 215–221, doi : 10.1016/S0166-218X(00)00178-5 , MR  1818238.
29. Malitz, Seth M. (1994), "Los gráficos con aristas E tienen número de página O (√ E ) ", Journal of Algorithms , 17 (1): 71–84, doi :10.1006/jagm.1994.1027, MR  1279269.
30. Malitz, Seth M. (1994), "Los gráficos del género g tienen número de página O (√ g ) ", Journal of Algorithms , 17 (1): 85–109, doi :10.1006/jagm.1994.1028, MR  1279270.
31. Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms , Algorithms and Combinatorics, vol. 28, Springer, págs. 321–328, doi :10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, Sr.  2920058.
32. Blankenship, R. (2003), Book Embeddings of Graphs , tesis doctoral, Departamento de Matemáticas, Universidad Estatal de Luisiana. Según lo citado por Nešetřil & Ossona de Méndez (2012).
33. Ozeki, Kenta; Nakamoto, Atsuhiro; Nozawa, Takayuki (2019), "Libro de incrustación de gráficos en el plano proyectivo" (PDF) , SIAM Journal on Discrete Mathematics , 33 (4): 1801–1836, doi :10.1137/16M1076174, MR  4013917
34. Bekos, Michael A.; Bruckdorfer, Till; Kaufmann, Michael; Raftopoulou, Chrysanthi (2015), "Los gráficos 1-planares tienen un grosor de libro constante", Algorithms – ESA 2015 , Lecture Notes in Computer Science, vol. 9294, Springer, págs. 130–141, doi :10.1007/978-3-662-48350-3_12, ISBN 978-3-662-48349-7.
35. Bekos, Michael; Kaufmann, Michael; Zielke, Christian (2015), "El problema de la incrustación de libros desde una perspectiva de resolución de SAT", Proc. 23.° Simposio internacional sobre dibujo de gráficos y visualización de redes (GD 2015) , págs. 113-125.
36. Barát, János; Matoušek, Jiří ; Wood, David R. (2006), "Los gráficos de grado acotado tienen un grosor geométrico arbitrariamente grande", Electronic Journal of Combinatorics , 13 (1): R3, doi : 10.37236/1029 , MR  2200531.
37. Dujmović, Vida ; Sidiropoulos, Anastasios; Wood, David R. (2015), "Expansores de 3 monótonos", arXiv : 1501.05020 [math.CO]{{cite arXiv}}: Mantenimiento de CS1: configuración anulada ( enlace ), mejorando un resultado anterior que mostraba la existencia de expansores con número de página constante de Bourgain, Jean (2009), "Expansores y expansión dimensional", Comptes Rendus Mathématique , 347 (7–8): 357–362, doi :10.1016/j.crma.2009.02.009, MR  2537230; Bourgain, Jean ; Yehudayoff, Amir (2013), "Expansión en y expansores monótonos", Análisis geométrico y funcional , 23 (1): 1–41, doi :10.1007/s00039-012-0200-9, MR  3037896, S2CID  121554827 ${\displaystyle \mathrm {SL} _{2}(\mathbb {R} )}$Véase también Galil, Zvi ; Kannan, Ravi ; Szemerédi, Endre (1989), "Sobre grafos de 3 empujes con separadores grandes", Combinatorica , 9 (1): 9–19, doi :10.1007/BF02122679, MR  1010295, S2CID  37506294; Dvir, Zeev; Wigderson, Avi (2010), "Expansores monótonos: construcciones y aplicaciones", Theory of Computing , 6 : 291–308, doi : 10.4086/toc.2010.v006a012 , MR  2770077.
38. Heath, Lenwood S.; Rosenberg, Arnold L. (1992), "Diseño de gráficos mediante colas", SIAM Journal on Computing , 21 (5): 927–958, doi :10.1137/0221055, MR  1181408.
39. Dujmović, Vida ; Wood, David R. (2004), "Sobre diseños lineales de gráficos", Discrete Mathematics & Theoretical Computer Science , 6 (2): 339–357, MR  2081479.
40. Wigderson, Avi (febrero de 1982), La complejidad del problema del circuito hamiltoniano para gráficos planares máximos (Informe técnico n.° 298), Departamento de Ingeniería Eléctrica y Computacional, Universidad de Princeton, a través del Instituto de Estudios Avanzados
41. Chung, Fan RK ; Leighton, Frank Thompson ; Rosenberg, Arnold L. (1987), "Incorporación de gráficos en libros: un problema de diseño con aplicaciones para el diseño VLSI" (PDF) , SIAM Journal on Algebraic and Discrete Methods , 8 (1): 33–58, doi :10.1137/0608002.
42. Unger, Walter (1992), "La complejidad de colorear gráficos circulares", STACS 92: 9º Simposio anual sobre aspectos teóricos de la informática, Cachan, Francia, 13-15 de febrero de 1992, Actas , Lecture Notes in Computer Science, vol. 577, Berlín: Springer, págs. 389-400, doi :10.1007/3-540-55210-3_199, ISBN 978-3-540-55210-9.
43. Unger, Walter (1988), "Sobre la coloración k de los grafos circulares", Actas del 5.º Simposio sobre Aspectos Teóricos de la Informática (STACS '88) , Lecture Notes in Computer Science, vol. 294, Springer-Verlag, págs. 61-72, doi :10.1007/BFb0035832, ISBN 3-540-18834-7.
44. Masuda, Sumio; Nakajima, Kazuo; Kashiwabara, Toshinobu; Fujisawa, Toshio (1990), "Minimización de cruces en incrustaciones lineales de gráficos", IEEE Transactions on Computers , 39 (1): 124–127, doi :10.1109/12.46286, MR  1032144.
45. Garey, MR ; Johnson, DS ; Miller, GL ; Papadimitriou, CH (1980), "La complejidad de colorear arcos circulares y cuerdas", SIAM Journal on Algebraic and Discrete Methods , 1 (2): 216–227, doi :10.1137/0601025, MR  0578325.
46. Hong, Seok-Hee ; Nagamochi, Hiroshi (2009), Two-page book embedding and clustered graph planarity (PDF) , Informe técnico (edición 2009-004), Departamento de Matemáticas Aplicadas y Física, Universidad de Kioto, Japón, archivado desde el original (PDF) el 24 de septiembre de 2020 , consultado el 16 de junio de 2014.
47. Angelini, Patrizio; Di Bartolomeo, Marco; Di Battista, Giuseppe (2013), "Implementación de un algoritmo de prueba de incrustación de libros particionados de 2 páginas", Graph Drawing: 20th International Symposium, GD 2012, Redmond, WA, EE. UU., 19-21 de septiembre de 2012, Documentos seleccionados revisados , Lecture Notes in Computer Science, vol. 7704, Springer, págs. 79-89, arXiv : 1209.0598 , doi :10.1007/978-3-642-36763-2_8, ISBN 978-3-642-36762-5, MR  3067219, S2CID  15360191.
48. Nešetřil & Ossona de Méndez (2012), Corolario 18.1, p. 401.
49. Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2008), "Grados y clases con expansión acotada. II. Aspectos algorítmicos", European Journal of Combinatorics , 29 (3): 777–791, arXiv : math/0508324 , doi :10.1016/j.ejc.2006.07.014, MR  2397336, S2CID  1139740.
50. Nešetřil y Ossona de Méndez (2012), Teorema 18.7, p. 405.
51. Rosenberg, Arnold L. (1986), "Integraciones de libros e integración a escala de obleas", Actas de la decimoséptima conferencia internacional del sudeste sobre combinatoria, teoría de grafos y computación (Boca Raton, Florida, 1986) , Congressus Numerantium, vol. 54, págs. 217-224, MR  0885282.
52. Knuth, Donald E. (1968), El arte de la programación informática, vol. 1 , Boston: Addison-Wesley, sección 2.2.1, ejercicios 4 y 5, ISBN 0-201-89683-4, MR  0286317, OCLC  155842391.
53. Kainen, Paul C. (1990), "El grosor del libro de un gráfico. II", Actas de la Vigésima Conferencia del Sureste sobre Combinatoria, Teoría de Grafos y Computación (Boca Raton, FL, 1989) , Congressus Numerantium, vol. 71, págs. 127-132, MR  1041623.
54. Wattenberg, M. (2002), "Diagramas de arco: visualización de la estructura en cadenas", Actas del Simposio IEEE sobre visualización de información (INFOVIS 2002) , págs. 110-116, doi :10.1109/INFVIS.2002.1173155, ISBN 0-7695-1751-X, Número de identificación del sujeto  881989.
55. Baur, Michael; Brandes, Ulrik (2005), "Reducción de cruces en diseños circulares", en van Leeuwen, Jan (ed.), Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Alemania, 21-23 de junio de 2004, Documentos revisados, Lecture Notes in Computer Science, vol. 3353, Springer, págs. 332–343, doi :10.1007/978-3-540-30559-0_28, ISBN 978-3-540-24132-4.
56. Angelini, Patrizio; Di Battista, Giuseppe; Frati, Fabrizio; Patrignani, Maurizio; Rutter, Ignaz (2012), "Prueba de la incrustabilidad simultánea de dos gráficos cuya intersección es un gráfico biconexo o conexo", Journal of Discrete Algorithms , 14 : 150–172, doi : 10.1016/j.jda.2011.12.015 , MR  2922068.
57. Wood, David R. (2002), "Incrustaciones de libros de grado acotado y dibujo de gráficos ortogonales tridimensionales", Graph Drawing: 9th International Symposium, GD 2001, Viena, Austria, 23-26 de septiembre de 2001, Documentos revisados , Lecture Notes in Computer Science, vol. 2265, Springer, Berlín, págs. 312-327, doi : 10.1007/3-540-45848-4_25 , ISBN 978-3-540-43309-5, Sr.  1962433.
58. Saaty, Thomas L. (1964), "El número mínimo de intersecciones en grafos completos", Actas de la Academia Nacional de Ciencias de los Estados Unidos de América , 52 (3): 688–690, Bibcode :1964PNAS...52..688S, doi : 10.1073/pnas.52.3.688 , MR  0166772, PMC 300329 , PMID  16591215 .
59. Nicholson, TAJ (1968), "Procedimiento de permutación para minimizar el número de cruces en una red", Actas de la Institución de Ingenieros Eléctricos , 115 : 21–26, doi :10.1049/piee.1968.0004, MR  0311416.
60. Miyauchi, Miki (2006), "Incorporación topológica de libros de grafos bipartitos", 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.
61. Giordano, Francesco; Liotta, Giuseppe; Mchedlidze, Tamara; Symvonis, Antonios (2007), "Computing rising topological book embeddings of rising planar digraphs", Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japón, 17-19 de diciembre de 2007, Actas , Lecture Notes in Computer Science, vol. 4835, Springer, págs. 172-183, doi :10.1007/978-3-540-77120-3_17, ISBN 978-3-540-77118-0.
62. He, Hongmei; Sykora, Ondrej (2004), "Nuevos algoritmos de dibujo circular", Actas del Taller sobre Tecnologías de la Información: Aplicaciones y Teoría (ITAT), Eslovaquia, 15-19 de septiembre de 2004.
63. Shahrokhi, Farhad; Sýkora, Ondrej; Székely, László A.; Vrt'o, Imrich (1995), "Incrustaciones de libros y cruces de números", Graph-Theoretic Concepts in Computer Science: 20th International Workshop, WG '94, Herrsching, Alemania, 16-18 de junio de 1994, Actas , Lecture Notes in Computer Science, vol. 903, Springer, págs. 256-268, doi :10.1007/3-540-59071-4_53, ISBN 978-3-540-59071-2.
64. Bannister, Michael J.; Eppstein, David ; Simons, Joseph A. (2013), "Tratabilidad de parámetros fijos de minimización de cruces de casi-árboles", Graph Drawing: 21st International Symposium, GD 2013, Burdeos, Francia, 23-25 ​​de septiembre de 2013, Documentos seleccionados revisados , Lecture Notes in Computer Science, vol. 8242, págs. 340-351, arXiv : 1308.5741 , doi :10.1007/978-3-319-03841-4_30, ISBN 978-3-319-03840-7, S2CID10142319 ​.
65. Bannister, Michael J.; Eppstein, David (2014), "Minimización cruzada para dibujos de grafos de 1 y 2 páginas con ancho de árbol acotado", Proc. 22nd Int. Symp. Graph Drawing (GD 2014) , Lecture Notes in Computer Science, vol. 8871, Springer-Verlag, págs. 210–221, arXiv : 1408.6321 , doi :10.1007/978-3-662-45803-7_18, ISBN 978-3-319-12567-1, Sr.  3333228.
66. 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, 7-9 de abril de 2007, Documentos seleccionados revisados ​​(PDF) , Lecture Notes in Computer Science, vol. 4614, págs. 140-151, doi :10.1007/978-3-540-74450-4_13, ISBN 978-3-540-74449-8.
67. Clote, Peter; Dobrev, Stefan; Dotu, Ivan; Kranakis, Evangelos; Krizanc, Danny; Urrutia, Jorge (2012), "Sobre el número de página de las estructuras secundarias del ARN con pseudonudos", Journal of Mathematical Biology , 65 (6–7): 1337–1357, doi :10.1007/s00285-011-0493-6, PMID  22159642, S2CID  8700502.
68. Pavan, A.; Tewari, Raghunath; Vinodchandran, NV (2012), "Sobre el poder de la unambigüedad en el espacio logarítmico", Computational Complexity , 21 (4): 643–670, arXiv : 1001.2034 , doi :10.1007/s00037-012-0047-3, MR  2988774, S2CID  8666071.
69. Galil, Zvi ; Kannan, Ravi ; Szemerédi, Endre (1989), "Sobre separadores no triviales para gráficos de k páginas y simulaciones mediante máquinas de Turing de una cinta no deterministas", Journal of Computer and System Sciences , 38 (1): 134–149, doi : 10.1016/0022-0000(89)90036-6.
70. McKenzie, Thomas; Overbay, Shannon (2010), "Incorporaciones de libros y divisores de cero", Ars Combinatoria , 95 : 55–63, MR  2656248.
71. Dynnikov, IA (1999), "Enfoque de tres páginas para la teoría de nudos. Codificación y movimientos locales", Rossiĭskaya Akademiya Nauk , 33 (4): 25–37, 96, doi :10.1007/BF02467109, MR  1746427, S2CID  121089736.
72. Dynnikov, IA (2001), "Una nueva forma de representar enlaces, formalismo unidimensional y tecnología de desenredo", Acta Applicandae Mathematicae , 69 (3): 243–283, doi :10.1023/A:1014299416618, MR  1885279, S2CID  116488382.