Libro de inversión

Una incrustación de libro en la teoría de grafos es una generalización de una incrustación plana de un gráfico a una incrustación en un libro : un conjunto de semiplanos que tienen la misma línea recta como límite. Por lo general, se requiere que los vértices del gráfico se encuentren en este límite y los bordes deben estar dentro de la misma página. El grosor del libro (o número de páginas ) de un gráfico es el número más pequeño de semiplanos para todas las incrustaciones de libros del gráfico. [1] La incrustación de libros se usa para varias otras invariantes de gráficos , incluido el ancho de página [2] y el número de cruces de libros [3] .

Cualquier gráfico con n vértices tiene un ancho de libro como máximo . Este límite es cercano para gráficos completos [1] . Sin embargo, subdividir cada borde puede reducir el grosor del libro a una cantidad proporcional a la raíz cuadrada de n . [4] Los gráficos con grosor de libro uno son gráficos planos exteriores , [1] y los gráficos con grosor de libro como máximo dos son sub-Hamiltonianos , que siempre son planos [2] . Cualquier gráfico plano tiene un grosor de libro que no exceda de cuatro [5] . Todas las familias de grafos cerrados de forma menor y, en particular, los grafos con un ancho de árbol acotado o un género acotado , también tienen un grosor de libro acotado [6] . Determinar el grosor exacto del libro de un gráfico dado es un problema NP-difícil , se conozca o no el orden de los vértices en el lomo [7] [8] . ${\ estilo de visualización \ lceil n/2 \ rceil}$

Una de las razones iniciales para estudiar el anidamiento de libros fue su aplicación en el diseño de VLSI , donde los vértices del anidamiento de libros representan componentes y los bordes representan conexiones entre componentes [7] [9] . Al visualizar gráficos, se pueden construir dos estilos estándar de representación de gráficos, diagramas de arco [10] y arreglos circulares [11] , mediante el anidamiento de libros. Los diversos puntos de inicio y fin del tráfico para peatones y vehículos que están regulados por un semáforo se pueden modelar matemáticamente como vértices de gráficos, con bordes que representan pares de inicio y fin, y la anidación de libros de este gráfico se puede usar para crear un semáforo. comportamiento para proporcionar regulación de tráfico con un número mínimo de estados de semáforo [12] . En problemas de bioinformática relacionados con estructuras de ARN , una incrustación de libro de una página representa la forma clásica de una estructura secundaria de ácido nucleico , y una incrustación de dos páginas representa pseudonudos [13] . La incrustación de libros también se usa en álgebra general [14] y teoría de nudos [15] [16] .

Las cuestiones abiertas con respecto a la inversión en libros son

¿El grosor del libro de un gráfico arbitrario está limitado por la función de sus subdivisiones [17]?
¿Es suficiente saber el orden de los vértices en el lomo para comprobar que el gráfico tiene un anidamiento de tres páginas [18]
¿Existe un grafo plano cuyo ancho de libro sea cuatro ? [19]
Cuántas intersecciones en el lomo se necesitan para una incrustación topológica de tres páginas (en este caso, los bordes pueden ir de una página a otra a lo largo del lomo) de un gráfico arbitrario [20] .

Historia

El nombre "libro" fue introducido por Persinger y Atneosen (CA Persinger, Gail Atneosen) en la década de 1960 [21] [22] [23] . Atneosen ya había utilizado la incrustación de gráficos en libros, pero el concepto formal de incrustación de libros fue formulado por C. Kainen y L. Taylor Ollman a principios de la década de 1970, y se agregaron algunas restricciones adicionales al método de incrustación: en su formulación, el los vértices del gráfico deben estar en el lomo de un libro, cada borde debe estar en una página (no se cruzan con el lomo) y dos bordes se cruzan solo en los vértices finales comunes [24] [25] .

Los hitos importantes en el desarrollo posterior de la incrustación de libros son la prueba de Michalis Giannakakis a fines de la década de 1980 de que el grosor del libro de los gráficos planos no supera los cuatro [26] [5] , y el descubrimiento a fines de la década de 1990 de una estrecha relación entre el libro incrustación y bioinformática . [13]

Definiciones

Un libro es un tipo especial de espacio topológico (también llamado abanico semiplanos) [21] [27] . Consiste en una sola línea recta ℓ llamada lomo [28] del libro, junto con un conjunto de uno o más semiplanos llamados páginas u hojas del libro. Cada semiplano debe tener la misma línea ℓ que su límite. Los libros con un número finito ( k ) de páginas se pueden anidar en un espacio tridimensional, por ejemplo, eligiendo un sistema de coordenadas rectangulares como la línea ℓ del eje z y como la página i - ésima (de k ) uno puede tomar un conjunto de puntos p tal que el segmento más corto , que conecta p con el eje z , tiene un ángulo de 2π i / k con respecto al plano xz [1] .

La visualización de un libro de gráfico finito G en el libro B es un dibujo del gráfico G en B , de modo que cualquier vértice de G se dibuja en el lomo B , y cualquier borde de G se dibuja como una curva que se encuentra dentro de una página de B. El número de intersecciones del libro de k páginas de un gráfico G es el número mínimo de intersecciones en un dibujo en un libro de k páginas [3] .

Una incrustación de libro de un gráfico G en B es una incrustación de un gráfico G en un espacio B. Es decir, es un dibujo de un gráfico G en B en el que las aristas no se cortan. Cualquier gráfico finito tiene un libro incrustado en un libro con un número suficientemente grande de páginas. Por ejemplo, siempre es posible anidar cada borde en su propia página. El grosor del libro , el número de páginas o el número de pila del gráfico G es el número mínimo de páginas necesario para anidar un libro del gráfico G. Otro parámetro que mide la calidad del adjunto de un libro, además del número de páginas, es el ancho de página . Este es el número máximo de bordes que cruza el 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), este es el tamaño máximo de un subconjunto de bordes tal que los intervalos definidos en el lomo por los extremos de los bordes se intersecan [2] [29] [30] .

Es esencial para estas definiciones que los bordes puedan estar en una sola página. Como ya señaló Ameosen, si los bordes pueden pasar de una página a otra (a través del lomo), entonces cualquier gráfico puede incrustarse en un libro de tres páginas [22] [31] [20] . Sin embargo, para una incrustación de libro topológica de tres páginas , en la que se permite la intersección de la columna, sigue siendo un problema interesante determinar el número de intersección de la columna más pequeño que permite que el gráfico se incruste en un libro [20] [32] .

Gráficos específicos

Como se muestra en la primera figura, el grosor del libro del gráfico completo es tres. Debido a que no es plano, el grosor de su libro es mayor que dos, pero hay un libro anidado con tres páginas. El grosor del libro de cualquier gráfico de vértice completo es exactamente . Este resultado da un límite superior en el grosor máximo del libro de cualquier gráfico con vértices [1] . El número de intersección de dos páginas del gráfico completo es $K_{5}$ $n\geq 4$ ${\ estilo de visualización \ lceil n/2 \ rceil}$ $norte$ $K_n$

(1/4)\left\lfloor {\frac {n}{2}}\right\rfloor \left\lfloor {\frac {n-1}{2}}\right\rfloor \left\lfloor {\frac {n-2}{2}}\derecha\rpiso \izquierda\lpiso {\frac {n-3}{2}}\derecha\rpiso ,

lo cual es consistente con la conjetura no probada de Anthony Hill . Es decir, si la conjetura de Hill es cierta, entonces el dibujo de este gráfico que minimiza el número de intersecciones es un dibujo de dos páginas [33] .

El grosor del libro de un gráfico bipartito completo es casi igual : para cada vértice de una parte más pequeña, puede organizar los bordes incidentes en estos vértices en su propia página. Este límite no siempre es estricto. Por ejemplo, tiene un grosor de libro de tres, no de cuatro. Sin embargo, cuando los dos lados de la gráfica están muy desequilibrados, c , el grosor del libro es exactamente . [1] [34] El grosor de los libros de gráficas binarias de De Bruijn , gráficas de intercambio mezcladas y redes cúbicas con ciclos (cuando estas gráficas son lo suficientemente grandes para no ser planas) es exactamente tres. [35] $K_{{a,b}}$ ${\displaystyle \min\{a,b\))$ $K_{4,4}$ $b>a(a-1)$ $K_{{a,b}}$ $a$

Propiedades

Comportamiento de subdivisión

Problemas no resueltos en Matemáticas : ¿Puede el grosor del libro de un gráfico estar limitado por una función del grosor del libro de las subdivisiones?

Dividir cada borde de un gráfico en rutas de dos bordes agregando nuevos vértices para cada borde a veces puede aumentar el grosor del libro (por ejemplo, un diamante tiene un grosor de libro de uno, pero su subdivisión tiene un grosor de libro de dos). Sin embargo, dicha subpartición también puede reducir significativamente el grosor del libro del gráfico después de la partición. Por ejemplo, el grosor del libro de un gráfico completo K n es Θ( n ) es proporcional al número de sus vértices, pero dividir cada borde en dos da una subdivisión con un grosor del libro mucho menor, solo O(√ n ). [4] . A pesar de la existencia de ejemplos como el anterior, Blankenship y Oporowski [31] conjeturaron que el grosor del libro de las subdivisiones no puede ser sustancialmente menor que el del gráfico original. En particular, asumieron que existe alguna función f , que para cualquier gráfico G y gráfico H obtenido reemplazando cada borde de G con un camino de dos bordes, si el grosor del libro del gráfico H es t , entonces el grosor del libro del gráfico G no excede f ( t ). [31] En 2013 , la conjetura de Blankenship-Oporowski seguía sin probarse. [17]

Planaridad y planaridad exterior

El grosor del libro de un gráfico G dado no excede de 1 si y sólo si G es plano exterior . Un grafo plano exterior 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 tales gráficos, colocar los vértices en el mismo orden a lo largo del lomo en el que aparecen en la cara exterior (cuando un vértice reaparece en la cara exterior, solo se toma una copia del vértice) produce una incrustación de gráfico de una página. Por el contrario, el anidamiento de un libro de una página es automáticamente plano exterior: si el gráfico está anidado en una página, al agregar un segundo medio plano se obtiene un plano completo, y la cara exterior contendrá todo el medio plano agregado, con todos los vértices sobre esta cara exterior [1] [2] .

Todo libro empotrable con dos páginas es un caso especial de empotramiento plano, ya que la unión de dos páginas de libro es un espacio topológicamente equivalente a un plano. Por lo tanto, cualquier gráfico con grosor de libro dos es automáticamente plano . Más precisamente, el grosor del libro de un gráfico G es como máximo dos si y solo si G es un subgrafo de un gráfico plano que tiene un ciclo hamiltoniano [1] . Dado un gráfico con un libro incrustado de dos páginas, el gráfico se puede extender a un gráfico hamiltoniano plano agregando (en cualquier página) bordes adicionales entre dos vértices consecutivos a lo largo del lomo, si aún no están conectados por un borde, y entre el primer y último vértice de la columna vertebral. El gráfico de Goldner-Harari ofrece un ejemplo de un gráfico plano que no tiene un grosor de libro dos: es un gráfico plano máximo , por lo que es imposible agregar un borde mientras se mantiene la planaridad, y el gráfico no tiene un hamiltoniano. ciclo [1] . Debido al requisito de tener ciclos hamiltonianos, los gráficos que permiten el anidamiento de dos páginas se conocen como gráficos sub-hamiltonianos [2] .

Todos los gráficos planos con grado máximo como máximo cuatro tienen una profundidad de incrustación de libro como máximo dos. [36] . Los 3 árboles planos tienen un ancho de libro máximo de tres [37] . Todos los gráficos planos tienen un grosor de libro que no excede cuatro [26] [5] . Como afirmó Michalis Yannakakis en 1986 [26] , hay gráficos planos con un grosor de incrustación de libro exactamente igual a cuatro, pero nunca se ha publicado una prueba detallada de esta afirmación, anunciada en [5] . Por esta razón, Duimovich [19] marcó como no resuelto el problema de determinar el grosor máximo de un libro incrustado de grafos planos [19] .

Relación con otros gráficos invariantes

El grosor del libro está relacionado con el grosor del gráfico , el número de gráficos planos que se necesitan para cubrir los bordes de un gráfico dado. Un gráfico G tiene espesor θ si se puede incrustar en un plano, y los bordes se pueden colorear en colores θ de tal manera que los bordes del mismo color no se intersecan. De manera similar, un gráfico G tiene un ancho de libro θ si se puede dibujar en un semiplano con vértices en el límite del semiplano y con bordes coloreados en colores θ sin cruzar bordes del mismo color. Con esta formulación, los bordes del mismo color corresponden a las páginas del archivo adjunto. Sin embargo, el grosor del gráfico y el grosor del libro pueden diferir significativamente: hay divisiones de gráficos completos que tienen un grosor de libro ilimitado [31] [20] [4] , a pesar de que el grosor del gráfico es igual a dos [4] .

Los gráficos con ancho de árbol k tienen un ancho de libro como máximo k + 1 [19] [38] y este límite se alcanza para k > 2. [19] . Los gráficos con m bordes tienen un ancho de libro O(√ m ) [39] , y los gráficos con género g tienen un ancho de libro O(√ g ) [40] . En términos más generales, cualquier familia de grafos cerrados menores tiene un grosor de libro acotado [6] [41] .

Cualquier menor que se contrae de un gráfico de grosor de libro acotado es un gráfico disperso cuya relación de borde a vértice está limitada por una constante que depende solo de la profundidad del menor y del grosor del libro. Es decir, en la terminología de Nexetril [6] , los gráficos con grosor de libro acotado tienen un crecimiento acotado [6] . Sin embargo, incluso los gráficos con un grado de gráfico acotado, un requisito de restricción de crecimiento sustancialmente mayor, pueden tener un grosor de libro ilimitado [42] .

Debido a que los dos gráficos de grosor de libro son gráficos planos, satisfacen el teorema de partición plana : tienen separadores, subconjuntos de vértices cuya eliminación divide el gráfico en partes con un máximo de 2 n /3 vértices en cada parte, con solo O(√ n ) vértices en separador. Aquí n significa el número de vértices del gráfico. Sin embargo, hay gráficos con grosor de libro tres que no tienen separadores de tamaño sublineales [43] .

Los bordes de una página de un archivo adjunto se comportan como una pila . Esto se puede formalizar considerando una secuencia arbitraria de operaciones push y pop (empujar y hacer estallar) en la pila y formar un gráfico en el que las operaciones de la pila corresponden a los vértices del gráfico ubicado en el lomo del libro insertado en el orden de las operaciones. Si ahora dibujamos un borde de cada operación pop que extrae un objeto x de la pila a la operación push que empuja ese elemento a la pila, el gráfico resultante automáticamente tendrá una anidación de una página. Por esta razón, el número de páginas de un gráfico también se denomina número de pila . Por analogía, los investigadores definen la incrustación de un gráfico siguiente como un dibujo de un gráfico en un libro en el que dos bordes cualesquiera de la página se cruzan o cubren intervalos que no se cruzan en el lomo. Tales incrustaciones corresponden de alguna manera a las colas , y el número mínimo de páginas requeridas para cada incrustación de gráficos se denomina número de colas [6] [44] [45] .

Complejidad computacional

Determinar el grosor de la incrustación de un libro es un problema NP-difícil . Esto se deriva del hecho de que encontrar un ciclo hamiltoniano en grafos planares máximos es un problema NP-completo . El grosor de la incrustación de libro de un gráfico plano máximo es dos si y solo si existe un camino hamiltoniano. Por lo tanto, determinar que el grosor de la incrustación del libro de un gráfico plano máximo dado es dos también es un problema NP-completo. [7]

Si el orden de los vértices a lo largo del lomo en el anidamiento de libros está predeterminado, se puede encontrar un anidamiento de dos páginas (si existe) en tiempo lineal como una opción de prueba de planaridad para un gráfico obtenido al extender un gráfico dado mediante la creación de un bucle que conecta vértices a lo largo de la columna vertebral [13] . Unger afirmó que encontrar una incrustación de tres páginas con un orden de vértices predeterminado podría hacerse en tiempo polinomial , aunque su descripción de este resultado carece de una serie de detalles esenciales [18] . Sin embargo, para los gráficos que requieren cuatro o más páginas, el problema de encontrar una incrustación con el menor número posible de páginas sigue siendo NP-difícil debido a la equivalencia con el problema NP-difícil de colorear gráficos circulares , gráficos de intersección de cuerdas circulares . Dado un grafo G con un orden fijo de vértices en la columna vertebral, colocar estos vértices en el mismo orden en el círculo y representar los bordes de G como segmentos da un conjunto de cuerdas que representan el grafo G. Ahora se puede formar un gráfico circular que tenga las cuerdas de este diagrama como vértices y pares de cuerdas que se intersecan como aristas. Colorear un gráfico circular da una partición de los bordes del gráfico G en subconjuntos que se pueden dibujar sin intersecciones en una página. Por lo tanto, una coloración óptima es equivalente a una incrustación óptima de libros. Dado que colorear un gráfico circular con cuatro o más colores es NP-difícil, y dado que cualquier gráfico circular puede generarse de esta manera a partir de algún problema de encontrar un libro incrustado, encontrar el libro incrustado óptimo también es un problema NP-difícil [8] [46] [47 ] . Para un orden fijo de vértices en el lomo bajo un anidamiento de dos páginas, es un problema NP-difícil minimizar el número de intersecciones si este número es distinto de cero [46] .

Si se desconoce el orden de los vértices en el lomo, pero se da la paginación de los bordes, es posible encontrar un anidamiento de 2 páginas (si existe) en tiempo lineal aplicando un algoritmo basado en árboles SPQR [48] [ 49] . Sin embargo, encontrar un anidamiento de 2 páginas es NP-completo si no se conoce el orden de los vértices en el lomo ni la paginación de los bordes. Encontrar el número de libro de las intersecciones de un gráfico también es NP-difícil debido a la NP-completitud del problema de comprobar si el número de intersecciones del libro de dos páginas es cero.

El problema de isomorfismo de subgrafo , que consiste en determinar si un gráfico de tamaño limitado de algún tipo se encuentra como un subgráfico de un gráfico más grande, se puede resolver en tiempo lineal si el gráfico más grande tiene un grosor de incrustación de libro acotado. Lo mismo es cierto para determinar si un gráfico de algún tipo es un subgráfico generado de un gráfico más grande, o si tiene un homeomorfismo con el gráfico más grande [50] [51] . Por la misma razón, el problema de verificar si un gráfico con grosor de libro acotado satisface una fórmula lógica de primer orden dada es solucionable con respecto a un parámetro fijo [52] .

Aplicaciones

Informática multiprocesador tolerante a fallos

Una de las principales razones para estudiar la incrustación de libros (según Chang, Leighton y Rosenberg [7] ) es su uso en el desarrollo de VLSI para crear sistemas multiprocesador tolerantes a fallas . En el sistema DIOGENES desarrollado por estos autores, los procesadores de un sistema multiprocesador están organizados en una cadena lógica correspondiente al lomo del libro (aunque no tienen por qué estar ubicados en línea recta físicamente en el diagrama ). Los enlaces de comunicación de estos procesadores se agrupan en "paquetes" que corresponden a las páginas de un libro y funcionan como pilas : conectar uno de los procesadores al comienzo de la línea de comunicación empuja hacia arriba todas las conexiones anteriores en el paquete y conectar otro procesador al final de la línea de comunicación lo conecta a uno de los procesadores inferiores en el haz y empuja todo lo que queda hacia abajo. Debido a este comportamiento de apilamiento, un solo paquete puede servir a un conjunto de líneas de comunicación que forman los bordes de una sola página de un libro adjunto. Al organizar los enlaces de esta manera, se puede implementar una amplia gama de topologías en las que no importa qué procesador falle, siempre que queden suficientes procesadores en la red. Las topologías de red que puede organizar un sistema de este tipo son exactamente aquellas que tienen el tamaño de un libro, sin exceder el número de paquetes disponibles [7] .

Clasificación de pila

Otra aplicación, señalada por Chang, Leighton y Rosenberg [7] , se refiere a la clasificación de permutaciones mediante pilas . Knuth demostró que un sistema que procesa un flujo de datos colocando elementos de entrada en la pila y luego colocándolos en el flujo de salida en el momento adecuado puede clasificar los datos si y solo si no hay permutaciones de patrones en el orden de los elementos originales [ 53 ] . Desde entonces, se ha trabajado mucho en este y otros problemas similares de clasificación de un flujo de datos con sistemas de colas y pilas más generales. En el sistema considerado por Chang, Leighton y Rosenberg, cada elemento del flujo de entrada debe colocarse en una de las pilas. Una vez que todos los datos se han insertado en las pilas, los elementos se eliminan de esas pilas (en el orden apropiado) al flujo de salida. Como señaló Chang et al., una permutación determinada puede ordenarse mediante un sistema de este tipo si y solo si algún gráfico obtenido de la permutación tiene un libro incrustado con un orden fijo de vértices a lo largo del lomo y el número de páginas no excede el número de páginas. pilas [7] .

Control de movimiento

Como describe Kainen [12] , la incrustación de libros se puede utilizar para describir las fases de los semáforos en una intersección controlada. En una intersección, los carriles de tráfico de entrada y salida (incluidos los extremos de los cruces de peatones y los carriles para bicicletas) se pueden representar como vértices de gráficos ubicados en el lomo de un archivo adjunto en el orden correspondiente al orden de entrada/salida del tráfico a lo largo de la intersección. intersección (en el sentido de las agujas del reloj). Los caminos a través de la intersección, donde se mueve el tráfico y los peatones desde el punto de entrada hasta el punto de salida, se pueden representar como los bordes de un gráfico no dirigido. Por ejemplo, este gráfico podría tener un borde desde un carril de entrada a un carril de salida perteneciente al mismo segmento de carretera, lo que representa un giro en U si se permiten giros en U en la intersección. Un subconjunto dado de dichos bordes representa un conjunto de caminos que se pueden seguir sin intersecciones si y solo si el subconjunto no contiene un par de bordes que se cruzan que están en la misma página de un libro anidado. Así, la incrustación de libro del gráfico describe la división de caminos en subconjuntos en los que el movimiento no se cruza, y el grosor de libro de este gráfico (con una incrustación fija en el lomo) da el número mínimo de fases de semáforo diferentes requeridas para un horario de semáforo que incluye todos los caminos posibles a través de la intersección [12] . Sin embargo, este modelo no es aplicable a sistemas de control de tráfico más complejos que no tienen un horario fijo.

Visualización de gráficos

La incrustación de libros también se usa a menudo para visualizar el flujo de datos de la red. Los dos esquemas estándar de visualización de gráficos , gráficos de arco [10] y gráficos circulares [11] , pueden considerarse inversiones en libros. La incrustación de libros también se puede utilizar para crear esquemas de clústeres [48] , incrustaciones simultáneas [54] y dibujos de gráficos en 3D [55] .

Un diagrama de arco [10] o una incrustación de línea [46] coloca los vértices del gráfico en una línea, y los bordes del gráfico se dibujan como semicírculos por encima y por debajo de esa línea, a veces permitiendo que los bordes sean segmentos de línea. Este estilo de dibujo corresponde a un libro anidado con una página (si todos los semicírculos están sobre la línea) o dos páginas (si se usan ambos lados de la línea) y se introdujo originalmente como una forma de estudiar el número de intersección de gráficos. [56] [57] Los gráficos planos que no tienen un anidamiento de libro de dos páginas se pueden dibujar de manera similar al permitir que los bordes se representen mediante dos semicírculos por encima y por debajo de una línea recta. Dichos dibujos no son incrustaciones de libros en términos de la definición habitual y se denominan incrustaciones topológicas de libros [58] . Para cualquier gráfico plano, siempre es posible encontrar una incrustación que cruce la columna como máximo una vez. [59] .

En otro estilo de dibujo, la disposición circular , los vértices del gráfico se colocan en un círculo y los bordes se dibujan dentro o fuera del círculo [11] . De nuevo, la disposición de los bordes dentro del círculo (por ejemplo, como segmentos de línea) corresponde al dibujo de un libro de una página, mientras que la disposición de los bordes a cada lado del círculo corresponde al dibujo de un libro de dos páginas [60] .

Para dibujos de una página de cualquier estilo, es importante mantener bajo el número de intersecciones para reducir el caos visual del dibujo. Minimizar el número de intersecciones es un problema NP-completo [46] , pero el problema se puede aproximar con la relación O (log 2 n ), donde n es el número de vértices [61] . La minimización del número de intersección de una o dos páginas es decidible con respecto a un parámetro fijo cuando se parametriza mediante el número ciclomático del gráfico dado [62] . También se han desarrollado métodos heurísticos para reducir la complejidad de las intersecciones, basados, por ejemplo, en el orden preciso de inserción de vértices y en la optimización local [11] .

Un libro de dos páginas incrustado con una distribución fija de bordes a lo largo de las páginas se puede representar como una especie de planaridad de grupo , en el que se debe dibujar un gráfico dado para que las partes del gráfico (dos subconjuntos de bordes) se organicen en la figura para reflejar su agrupación [48] . La incrustación de un libro de dos páginas también se usa para encontrar una incrustación de gráficos simultánea, en la que se dan dos gráficos en el mismo conjunto de vértices, y es necesario encontrar la ubicación de los vértices, en la que ambos gráficos se dibujan planamente usando una línea recta. segmentos [54] .

Los archivos adjuntos de libros que tienen más de dos páginas se utilizan para construir dibujos tridimensionales de gráficos. En particular, Wood usó la construcción de incrustaciones de libros, que preservan el bajo grado de cada vértice dentro de cada página, como un método para incrustar gráficos en una red tridimensional de pequeño volumen [55] .

ARN plegable

Al estudiar cómo se pliegan las moléculas de ARN para formar una estructura de ARN, la vista estándar de la estructura secundaria de un ácido nucleico se puede describir utilizando un diagrama como una cadena de bases (secuencia de ARN) dibujada a lo largo de una línea recta junto con un conjunto de arcos por encima de la línea que describen las bases pareadas de la estructura. . Es decir, aunque esta estructura tiene una apariencia tridimensional compleja, sus conexiones (si existe una estructura secundaria) pueden describirse mediante una estructura más abstracta, un inserto de libro de una página. Sin embargo, no todos los ARN se comportan de forma tan sencilla. Haslinger y Stadler propusieron una "estructura bisecundaria" para ciertos pseudonudos de ARN , que toman la forma de un anidamiento de un libro de dos páginas: la secuencia de ARN se dibuja nuevamente a lo largo de una línea recta, pero las bases emparejadas se dibujan como arcos arriba y abajo. debajo de esta línea. Para formar una estructura bisecundaria, el gráfico debe tener un grado que no exceda de tres: cada base puede estar en solo un borde del diagrama, así como en dos enlaces con bases vecinas en la secuencia. La ventaja de esta formulación incluye el hecho de que excluye estructuras que están realmente anudadas en el espacio y que cubre la mayoría de los pseudonudos de ARN conocidos [13] .

Dado que el orden en la columna vertebral se conoce inicialmente, la existencia de una estructura bisecundaria para bases pareadas dadas se verifica directamente. La tarea de distribuir aristas en dos páginas se puede formular como un caso especial del problema de satisfacibilidad de fórmulas booleanas en forma normal 2-conjuntiva o como un problema de comprobación de la bipartición de un gráfico circular cuyos vértices son bases apareadas, y los bordes describen el cruce entre pares de bases [13] . Otra forma más eficiente, como lo muestran Haslinger y Stadler [13] , de determinar que existe una estructura bisecundaria es por el hecho de que sucede si y solo si el gráfico de entrada (el gráfico formado al enlazar las bases en el orden siguiente y agregando pares de bases como aristas) es plano [13] . Este hecho permite reconocer una estructura bisecundaria en tiempo lineal como un caso especial de la prueba de planaridad .

Blin, Fertin, Rusu y Sinokvet utilizaron la relación entre estructuras secundarias y archivos adjuntos como parte de la prueba de que algunos problemas de comparación de estructuras secundarias de ARN son NP-difíciles [63] . Y si la estructura del ARN es terciaria en lugar de bisecundaria (es decir, si se requieren más de dos páginas en su diagrama), entonces determinar el número de páginas es nuevamente un problema NP-difícil [64] .

Teoría de la complejidad computacional

Paian, Tewari y Vinodsoandran utilizaron la incrustación de libros para estudiar la complejidad computacional del problema de accesibilidad en grafos dirigidos . Como señalaron, el problema de accesibilidad para gráficos dirigidos de dos páginas se puede resolver en un espacio logarítmico de un solo valor (análogo a la complejidad de la memoria logarítmica determinista de los problemas de clase UP ). Sin embargo, el problema de accesibilidad para gráficos dirigidos de tres páginas genera una complejidad de memoria logarítmica no determinista . Por lo tanto, la incrustación de libros parece estar estrechamente relacionada con las diferencias entre estas dos clases de complejidad [65] .

La existencia de expansores con un número constante de páginas [43] es un paso clave para demostrar que no existe una simulación subcuadrática en el tiempo de máquinas de Turing no deterministas de dos cintas mediante máquinas no deterministas de una sola cinta [66] .

Otras áreas de las matemáticas

Mackenzie y Overbey [14] estudiaron aplicaciones de grosor de libros en álgebra general utilizando gráficos derivados de los divisores de cero de un anillo local finito creando un vértice para cada divisor de cero y una arista para cada par de valores cuyo producto es cero [14] .

En una sucesión de artículos, Dynnikov estudió incrustaciones topológicas de nudos y enlaces en libros , demostrando que estas incrustaciones pueden describirse mediante una secuencia combinatoria de símbolos y que la equivalencia topológica de dos enlaces puede mostrarse mediante una secuencia de cambios locales en las incrustaciones [15 ] [16] .

Notas

↑ 1 2 3 4 5 6 7 8 9 Bernhart y Kainen, 1979 , págs. 320–331.
↑ 1 2 3 4 5 Heath, 1987 , págs. 198–218.
↑ 12 Shahrokhi et al, 1996 , págs. 413–424.
↑ 1 2 3 4 Eppstein, 2001 .
↑ 1 2 3 4 Yannakakis, 1989 , págs. 36–67.
↑ 1 2 3 4 5 Nešetřil, Ossona de Méndez, 2012 , págs. 321–328.
↑ 1 2 3 4 5 6 7 Chung et al, 1987 , págs. 33–58.
↑ 12 Unger , 1988 , págs. 61–72.
↑ Arnold L. Rosenberg. Actas de la decimoséptima conferencia internacional del sureste sobre combinatoria, teoría de grafos y computación (Boca Raton, Fla., 1986). - 1986. - T. 54. - S. 217-224. — (Congressus Numerantium). .
↑ 1 2 3 Wattenberg, 2002 , págs. 111–116.
↑ 1 2 3 4 Baur, Brandes, 2005 , págs. 332–343.
↑ 1 2 3 Kainen, 1990 , págs. 127–132.
↑ 1 2 3 4 5 6 7 Haslinger et al, 1999 , págs. 437–467.
↑ 1 2 3 McKenzie, Overbay, 2010 , págs. 55–63.
↑ 1 2 Dynnikov, 1999 , págs. 25–37, 96.
↑ 1 2 Dynnikov, 2001 , págs. 243–283.
↑ 12 Blankenship , Oporowski, 2009 .
↑ 1 2 Walter Unger. STACS 92: 9º Simposio Anual sobre Aspectos Teóricos de la Informática, Cachan, Francia, 13 al 15 de febrero de 1992, Actas. - Berlín: Springer, 1992. - T. 577. - S. 389-400. — (Apuntes de clase en informática). -doi : 10.1007 / 3-540-55210-3_199 . .
↑ 1 2 3 4 5 Dujmović, Wood, 2007 , págs. 641–670.
↑ 1 2 3 4 Enomoto, Miyauchi, 1999 , págs. 337–341.
↑ 12 Persinger , 1966 , págs. 169–173.
↑ 1 2 Atneosen, 1968 , p. 79.
↑ Gail H. Atneosen. Continua unidimensional de n hojas // Fundamenta Mathematicae . - 1972. - T. 74 , núm. 1 . — págs. 43–45 . .
↑ Paul C. Kainen. Gráficos y Combinatoria (Actas de la Conferencia Capital sobre Teoría de Gráficos y Combinatoria en la Universidad George Washington del 18 al 22 de junio de 1973) / Ruth A. Bari, Frank Harary. - 1974. - T. 406. - S. 76-108. — (Apuntes de clase en Matemáticas). .
↑ L. Taylor Ollmann. proc. Cuarta Conferencia del Sureste sobre Combinatoria, Teoría de Grafos y Computación / Frederick Hoffman, Roy B. Levow, Robert SD Thomas. - 1973. - T. VIII. - S. 459. - (Congressus Numerantium). .
↑ 1 2 3 Yannakakis, 1986 , págs. 104–108.
↑ TC Hales. Empaquetaduras de esfera. II // Geometría Discreta y Computacional. - 1997. - T. 18 , núm. 2 . — S. 135–149 . -doi : 10.1007/ PL00009312 . .
↑ Originalmente columna o espalda
↑ Elena Stohr. 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. - 1988. - T. 79 , núm. 2 . — S. 155–162 . - doi : 10.1016/0890-5401(88)90036-3 . .
↑ Elena Stohr. El ancho de página de grafos planos trivalentes // Matemáticas discretas . - 1991. - T. 89 , núm. 1 . — págs. 43–49 . - doi : 10.1016/0012-365X(91)90398-L . .
↑ 1 2 3 4 Blankenship, Oporowski, 1999 .
↑ Hikoe Enomoto, Miki Shimabara Miyauchi, Katsuhiro Ota. Límites inferiores para el número de cruces de bordes sobre la columna vertebral en un libro topológico incrustación de un gráfico // Matemáticas aplicadas discretas. - 1999. - T. 92 , núm. 2-3 . — S. 149–155 . - doi : 10.1016/S0166-218X(99)00044-X . .
↑ Bernardo M. Ábrego, Oswin Aichholzer, Silvia Fernández-Merchant, Pedro Ramos, Gelasio Salazar. Actas del 28º Simposio Anual sobre Geometría Computacional (SCG'12). - ACM, Nueva York, 2012. - S. 397-403. -doi : 10.1145/ 2261250.2261310 . .
↑ Para obtener resultados adicionales sobre el grosor del libro de Complete Bipartite Graphs, consulte Etienne de Klerk, Dmitrii V. Pasechnik, Gelasio Salazar. Dibujos de libros de grafos bipartitos completos // Matemática aplicada discreta. - 2014. - T. 167 . — S. 80–93 . -doi : 10.1016/ j.dam.2013.11.001 . .
↑ Toru Hasunuma, Yukio Shibata. Incorporación de redes de Bruijn, Kautz y shuffle-exchange en libros // Matemática aplicada discreta. - 1997. - T. 78 , núm. 1-3 . — S. 103–116 . - doi : 10.1016/S0166-218X(97)00009-7 . Yuuki Tanaka, Yukio Shibata En el número de página de los ciclos conectados al cubo // Matemáticas en Ciencias de la Computación. - 2010. - Vol. 3 , número. 1 . — S. 109–117 . -doi : 10.1007 / s11786-009-0012-y . Véase también Bojana Obrenic. Incrustación de gráficos de Bruijn y de intercambio aleatorio en cinco páginas // SIAM Journal on Discrete Mathematics. - 1993. - T. 6 , núm. 4 . — S. 642–654 . -doi : 10.1137/ 0406049 . .
↑ Bekos et al, 2014 , págs. 137–148.
↑ Lenny Heath. Actas del 25º Simposio Anual sobre Fundamentos de Ciencias de la Computación. - 1984. - S. 74-83. -doi : 10.1109/ SFCS.1984.715903 .
↑ Joseph L. Ganley, Lenwood S. Heath. El número de página de k -trees es O ( k ) // Matemática aplicada discreta. - 2001. - T. 109 , núm. 3 . — S. 215–221 . - doi : 10.1016/S0166-218X(00)00178-5 . .
↑ Seth M. Malitz. Los gráficos con bordes E tienen el número de página O (√ E ) // Journal of Algorithms : journal. - 1994. - julio ( vol. 17 , número 1 ). — págs. 71–84 . -doi : 10.1006/ jagm.1994.1027 .
↑ Seth M. Malitz. Los gráficos del género g tienen el número de página O (√ g ) // Journal of Algorithms. - 1994. - T. 17 , núm. 1 . — S. 85–109 . -doi : 10.1006/ jagm.1994.1028 . .
↑ R. Blankenship. Libro Embeddings of Graphs. — Departamento de Matemáticas, Universidad Estatal de Luisiana, 2003. . Citado por Neshetri.
↑ János Barát, Jiří Matoušek, David R. Wood. Los gráficos de grado acotado tienen un grosor geométrico arbitrariamente grande // Electronic Journal of Combinatorics. - 2006. - T. 13 , núm. 1 . — C. R3 . .
↑ 1 2 Vida Dujmovic, Anastasios Sidiropoulos, David R. Wood. 3-Expansores Monotono. -arXiv : 1501.05020 . _ , una mejora de un resultado anterior de Jean Bourgain. Expansores y expansión dimensional // Comptes Rendus Mathematique. - 2009. - T. 347 , núm. 7-8 . — S. 357–362 . -doi : 10.1016/ j.crma.2009.02.009 . ; Jean Bourgain, Amir Yehudayoff. Expansión en y expansores monótonos // Análisis Geométrico y Funcional. - 2013. - T. 23 , núm. 1 . — Pág. 1–41 . -doi : 10.1007/ s00039-012-0200-9 . ${\rm {SL}}_{2}(\mathbb {R} )$ . Véase también Zvi Gali, Ravi Kannan, Endre Szemerédi. En gráficos de 3 pulsaciones con grandes separadores // Combinatorica. - 1989. - T. 9 , núm. 1 . — págs. 9–19 . -doi : 10.1007/ BF02122679 . ; Zeev Dvir, Avi Wigderson. Expansores monótonos: construcciones y aplicaciones // Teoría de la Computación. - 2010. - T. 6 . — S. 291–308 . -doi : 10.4086 / toc.2010.v006a012 . .
↑ Lenwood S. Heath, Arnold L. Rosenberg. Disposición de gráficos mediante colas // SIAM Journal on Computing. - 1992. - T. 21 , núm. 5 . — S. 927–958 . -doi : 10.1137/ 0221055 . .
↑ Vida Dujmovic, David R. Wood. Sobre diseños lineales de gráficos // Matemáticas discretas y ciencias de la computación teórica. - 2004. - T. 6 , núm. 2 . — S. 339–357 . .
↑ 1 2 3 4 Masuda et al, 1990 , págs. 124–127.
↑ MR Garey, DS Johnson, GL Miller, CH Papadimitriou. La complejidad de colorear arcos circulares y cuerdas // SIAM Journal on Algebraic and Discrete Methods. - 1980. - Vol. 1 , número. 2 . — S. 216–227 . -doi : 10.1137/ 0601025 . .
↑ 1 2 3 Hong, Nagamochi, 2009 .
↑ Patrizio Angelini, Marco Di Bartolomeo, Giuseppe Di Battista. Dibujo de gráficos: 20º Simposio Internacional, GD 2012, Redmond, WA, EE. UU., 19 al 21 de septiembre de 2012, Documentos seleccionados revisados. - Springer, 2013. - T. 7704. - S. 79–89. — (Apuntes de clase en informática). -doi : 10.1007 / 978-3-642-36763-2_8 . .
↑ Nešetřil, Ossona de Méndez, 2008 , págs. 777–791.
↑ Nešetřil, Ossona de Mendez, 2012 , Corolario 18.1, p. 401.
↑ Nešetřil, Ossona de Mendez, 2012 , Teorema 18.7, p. 405.
↑ Donald E. Knuth. El arte de la programación informática vol. 1 . - Boston: Addison-Wesley, 1968. - ISBN 0-201-89683-4 . .
↑ 12 Angelini et al, 2012 , págs. 150–172.
↑ 12 Wood , 2002 , págs. 312–327.
↑ Thomas L. Saaty. El número mínimo de intersecciones en gráficos completos // Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . - 1964. - T. 52 . — S. 688–690 . -doi : 10.1073/ pnas.52.3.688 . .
↑ TAJ Nicholson. Procedimiento de permutación para minimizar el número de cruces en una red // Procedimientos de la Institución de Ingenieros Eléctricos. - 1968. - T. 115 . — P. 21–26 . -doi : 10.1049/ piee.1968.0004 . .
↑ Miki Miyauchi. Incrustación de libros topológicos de grafos bipartitos (inglés) // IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. - 2006. - vol. E89-A , edición. 5 . — pág. 1223–1226 . -doi : 10.1093 / ietfec/e89-a.5.1223 .
↑ Francesco Giordano, Giuseppe Liotta, Tamara Mchedlidze, Antonios Symvonis. Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japón, 17 al 19 de diciembre de 2007, Actas. - Springer, 2007. - T. 4835. - S. 172-183. — (Apuntes de clase en informática). -doi : 10.1007 / 978-3-540-77120-3_17 . .
↑ Hongmei He, Ondrej Sykora. Actas del taller sobre tecnologías de la información: aplicaciones y teoría (ITAT), Eslovaquia, 15 al 19 de septiembre de 2004. - 2004. .
↑ Farhad Shahrokhi, Ondrej Sýkora, László A. Székely, Imrich Vrt'o. Conceptos teóricos de gráficos en informática: 20.º taller internacional, WG '94, Herrsching, Alemania, 16 al 18 de junio de 1994, Actas. - Springer, 1995. - T. 903. - S. 256-268. — (Apuntes de clase en informática). -doi : 10.1007/ 3-540-59071-4_53 . .
↑ Michael J. Bannister, David Eppstein, Joseph A. Simons. Dibujo gráfico: 21.er Simposio Internacional, GD 2013, Burdeos, Francia, 23 al 25 de septiembre de 2013, Documentos seleccionados revisados. - 2013. - T. 8242. - S. 340-351. — (Apuntes de clase en informática). -doi : 10.1007 / 978-3-319-03841-4_30 . .
↑ Guillaume Blin, Guillaume Fertin, Irena Rusu, Christine Sinoquet. Combinatoria, Algoritmos, Metodologías Probabilísticas y Experimentales: Primer Simposio Internacional, ESCAPE 2007, Hangzhou, China, 7-9 de abril de 2007, Documentos seleccionados revisados. - 2007. - T. 4614. - S. 140-151. — (Apuntes de clase en informática). -doi : 10.1007 / 978-3-540-74450-4_13 . .
↑ Peter Clote, Stefan Dobrev, Ivan Dotu, Evangelos Kranakis, Danny Krizanc, Jorge Urrutia. En el número de página de estructuras secundarias de ARN con pseudonudos // Journal of Mathematical Biology. - 2012. - T. 65 , núm. 6–7 . - S. 1337-1357 . -doi : 10.1007/ s00285-011-0493-6 . .
↑ A. Pavan, Raghunath Tewari, NV Vinodchandran. Sobre el poder de la falta de ambigüedad en el espacio log // Complejidad Computacional. - 2012. - T. 21 , núm. 4 . — S. 643–670 . -doi : 10.1007/ s00037-012-0047-3 . .
↑ Zvi Galil, Ravi Kannan, Endre Szemerédi. Sobre separadores no triviales para gráficos de páginas k y simulaciones mediante máquinas de Turing de una cinta no deterministas // Journal of Computer and System Sciences. - 1989. - T. 38 , núm. 1 . — S. 134–149 . - doi : 10.1016/0022-0000(89)90036-6 . .

Literatura

C. A. Persinger. Subconjuntos de n -libros en E 3 // Pacific Journal of Mathematics. - 1966. - T. 18 . — S. 169–173 . -doi : 10.2140 / pjm.1966.18.169 .
Gail Adele Atneosen. Sobre la incrustabilidad de compacta en n -books: propiedades intrínsecas y extrínsecas. - Michigan State University , 1968. - S. 79. - (Tesis doctoral).
Frank R. Bernhart, Paul C. Kainen. El grosor del libro de un gráfico // Journal of Combinatorial Theory . - 1979. - T. 27 , núm. 3 . — S. 320–331 . - doi : 10.1016/0095-8956(79)90021-2 .
Mihalis Yannakakis. Actas del 18º Simposio ACM sobre Teoría de la Computación (STOC '86). - 1986. - S. 104-108. — ISBN 0-89791-193-8 . -doi : 10.1145/ 12130.12141 .
Lenwood S. Heath. Incrustación de gráficos planos exteriores en libros pequeños // SIAM Journal on Algebraic and Discrete Methods. - 1987. - T. 8 , núm. 2 . — S. 198–218 . -doi : 10.1137/ 0608018 .
Fan RK Chung, Frank Thompson Leighton, Arnold L. Rosenberg. Incrustación de gráficos en libros: un problema de diseño con aplicaciones al diseño VLSI // SIAM Journal on Algebraic and Discrete Methods. - 1987. - T. 8 , núm. 1 . — págs. 33–58 . -doi : 10.1137/ 0608002 .
Walter Unger. Actas del 5º Simposio sobre Aspectos Teóricos de la Informática (STACS '88). - Springer-Verlag, 1988. - T. 294. - S. 61–72. — (Apuntes de clase en informática). -doi : 10.1007/ BFb0035832 .
Mihalis Yannakakis. Incrustación de gráficos planos en cuatro páginas // Journal of Computer and System Sciences. - 1989. - T. 38 . — págs. 36–67 . - doi : 10.1016/0022-0000(89)90032-9 .
Paul C. Kainen. Actas de la Vigésima Conferencia del Sureste sobre Combinatoria, Teoría de Grafos y Computación (Boca Raton, FL, 1989). - 1990. - T. 71. - S. 127-132. — (Congressus Numerantium).
Sumio Masuda, Kazuo Nakajima, Toshinobu Kashiwabara, Toshio Fujisawa. Minimización de cruces en incrustaciones lineales de gráficos // Transacciones IEEE en computadoras. - 1990. - T. 39 , núm. 1 . — S. 124–127 . -doi : 10.1109/ 12.46286 .
Farhad Shahrokhi, László A. Szekely, Ondrej Sýkora, Imrich Vrťo. El número de cruce de libros de un gráfico // Journal of Graph Theory. - 1996. - T. 21 , núm. 4 . — S. 413–424 . - doi : 10.1002/(SICI)1097-0118(199604)21:4<413::AID-JGT7>3.3.CO;2-5 .
Hikoe Enomoto, Miki Shimabara Miyauchi. Incrustación de gráficos en un libro de tres páginas con cruces de bordes O ( M log N ) sobre el lomo // SIAM Journal on Discrete Mathematics. - 1999. - T. 12 , núm. 3 . — S. 337–341 . -doi : 10.1137/ S0895480195280319 .
Christian Haslinger, Peter F. Stadler. Estructuras de ARN con pseudonudos: propiedades gráficas teóricas, combinatorias y estadísticas // Boletín de biología matemática. - 1999. - T. 61 , núm. 3 . — S. 437–467 . -doi : 10.1006/ bulm.1998.0085 .
I. A. Dynnikov. Aproximación de tres páginas a la teoría de nudos. Codificación y mociones locales // Rossiĭskaya Akademiya Nauk. - 1999. - T. 33 , núm. 4 . — S. 25–37, 96 . -doi : 10.1007/ BF02467109 .
Robin Blankenship, Bogdan Oporowski. Dibujar subdivisiones de gráficos bipartitos completos y completos en libros. - Departamento de Matemáticas, Universidad Estatal de Luisiana, 1999. - (Informe Técnico 1999-4).
David Epstein. Separación del grosor geométrico del grosor del libro . - 2001. - Pág. 20 . -arXiv : matemáticas.CO / 0109195 .
I. A. Dynnikov. Una nueva forma de representar enlaces, formalismo unidimensional y tecnología de desenredado // Acta Applicandae Mathematicae. - 2001. - T. 69 , núm. 3 . — S. 243–283 . -doi : 10.1023/A : 1014299416618 .
Martín M. Wattenberg. Actas del Simposio IEEE sobre visualización de información (INFOVIS 2002). - 2002. - S. 110-116. -doi : 10.1109/ INFVIS.2002.1173155 .
David R Wood. Dibujo gráfico: 9º Simposio internacional, GD 2001, Viena, Austria, 23 al 26 de septiembre de 2001, Documentos revisados. - Berlín: Springer, 2002. - T. 2265. - S. 312-327. — (Apuntes de clase en informática). -doi : 10.1007/ 3-540-45848-4_25 .
Michael Baur, Ulrik Brandes. Conceptos teóricos de gráficos en informática: 30.° taller internacional, WG 2004, Bad Honnef, Alemania, 21 al 23 de junio de 2004, Documentos revisados / van Leeuwen. - Springer, 2005. - T. 3353. - S. 332-343. — (Apuntes de clase en informática). -doi : 10.1007 / 978-3-540-30559-0_28 .
Vida Dujmovic, David R. Wood. Grafique los parámetros de ancho de árbol y grosor geométrico // Geometría discreta y computacional. - 2007. - T. 37 , núm. 4 . — S. 641–670 . -doi : 10.1007/ s00454-007-1318-7 .
Jaroslav Nešetřil, Patrice Ossona de Méndez. Graduados y clases con expansión acotada. II. Aspectos algorítmicos // European Journal of Combinatorics. - 2008. - T. 29 , núm. 3 . — S. 777–791 . -doi : 10.1016/ j.ejc.2006.07.014 .
Robin Blankenship, Bogdan Oporowski. Libro Grosor de las subdivisiones (inglés) // Jardín de problemas abiertos: sitio / David Wood. - 2009. - 19 de enero.
Seok-Hee Hong, Hiroshi Nagamochi. Incrustación de libros de dos páginas y planaridad de gráficos agrupados. — Informe técnico 2009-004. — Departamento of Applied Mathematics and Physics, University of Kyoto, Japón, 2009. - (Informe técnico).
Thomas McKenzie, Shannon Overbay. Libro incrustaciones y divisores de cero // Ars Combinatoria. - 2010. - T. 95 . — págs. 55–63 .
Jaroslav Nešetřil, Patrice Ossona de Méndez. Sparity: gráficos, estructuras y algoritmos. - Springer, 2012. - T. 28. - S. 321–328. — (Algoritmos y Combinatoria). — ISBN 978-3-642-27874-7 . -doi : 10.1007 / 978-3-642-27875-4 .
Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Ignaz Rutter. Prueba de la capacidad de integración simultánea de dos gráficos cuya intersección es un gráfico biconectado o conectado // Journal of Discrete Algorithms. - 2012. - T. 14 . — S. 150–172 . -doi : 10.1016/ j.jda.2011.12.015 .
Michael A. Bekos, Martin Gronemann, Chrysanthi N. Raftopoulou. Actas del 31º Simposio sobre Aspectos Teóricos de las Ciencias de la Computación. - 2014. - S. 137-148. -doi : 10.4230 / LIPIcs.STACS.2014.137 .