En la teoría de grafos , la incrustación de un libro es una generalización de la incrustación plana de un gráfico a incrustaciones en un libro , una colección de semiplanos que tienen la misma línea como límite. Por lo general, se requiere que los vértices del gráfico se encuentren en esta línea de límite, llamada columna , y se requiere que los bordes permanezcan dentro de un solo semiplano. El grosor del libro de un gráfico es el menor número posible de semiplanos para cualquier inclusión de libro en el gráfico. El grosor del libro también se denomina número de página , número de pila o grosor exterior fijo.. Las incrustaciones de libros también se han utilizado para definir varios otros invariantes de gráficos, incluido el ancho de página y el número de cruce de libros.
Cada gráfico con n vértices tiene un grosor de libro como máximo, y esta fórmula da el grosor exacto del libro para gráficos completos . Los gráficos con un grosor de libro uno son los gráficos del plano exterior . Las gráficas con un grosor de libro como máximo dos son las gráficas subhamiltonianas , que siempre son planas ; de manera más general, cada gráfico plano tiene un grosor de libro como máximo de cuatro. Todas las familias de grafos cerrados menores , y en particular los grafos con ancho de árbol acotado o género acotado , también tienen grosor de libro acotado. Es NP-difícil determinar el grosor exacto del libro de un gráfico dado, con o sin conocer un orden de vértice fijo a lo largo del lomo del libro.
Una de las motivaciones originales para estudiar incrustaciones de libros involucró aplicaciones en el diseño de VLSI , en las que los vértices de una incrustación de libros representan componentes de un circuito y los cables representan conexiones entre ellos. La incrustación de libros también tiene aplicaciones en el dibujo de gráficos , donde dos de los estilos de visualización estándar para gráficos, diagramas de arco y diseños circulares , se pueden construir utilizando incrustaciones de libros.
En la planificación del transporte , las diferentes fuentes y destinos del tráfico peatonal y de vehículos que se encuentran e interactúan en un semáforo se pueden modelar matemáticamente como los vértices de un gráfico, con bordes que conectan diferentes pares de origen y destino. Se puede utilizar un libro que incluya este gráfico para diseñar un horario 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ñales. En los problemas de bioinformática que involucran la estructura de plegado del ARN , las incrustaciones de libros de una sola página representan formas clásicas de estructura secundaria de ácido nucleico , y las incrustaciones de libros de dos páginas representan pseudonudos . Otras aplicaciones de las incrustaciones de libros incluyen el álgebra abstracta y la teoría de nudos .
Hay varios problemas abiertos relacionados con el grosor de los libros. Se desconoce si el grosor del libro de un gráfico arbitrario puede estar acotado por una función del grosor del libro de sus subdivisiones . Probar la existencia de una incrustación de libro de tres páginas de un gráfico, dado un orden fijo de los vértices a lo largo del lomo de la incrustación, tiene una complejidad computacional desconocida: no se sabe que se pueda resolver en tiempo polinómico ni que sea NP-hard . Y, aunque cada gráfico plano tiene un grosor de libro como máximo de cuatro, se desconoce si existe un gráfico plano cuyo grosor de libro sea exactamente cuatro.
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ó incrustaciones de gráficos en libros. Las incrustaciones que estudió utilizaron la misma definición que las incrustaciones de gráficos en cualquier otro espacio topológico: los vértices están representados por puntos distintos, los bordes están representados por curvas y la única forma en que dos bordes pueden cruzarse es que se encuentren en un punto final común.
A principios de la década de 1970, Paul C. Kainen y L. Taylor Ollmann desarrollaron un tipo de incrustación más restringido que llegó a utilizarse en la mayoría de las investigaciones posteriores. En su formulación, los vértices del gráfico deben colocarse a lo largo del lomo del libro y cada borde debe estar en una sola página. [3] [4] Hitos importantes en el desarrollo posterior de incrustaciones de libros incluyen la prueba de Mihalis Yannakakis a fines de la década de 1980 de que las gráficas planas tienen un grosor de libro como máximo cuatro, [5] [6] y el descubrimiento a fines de la década de 1990 de cerca conexiones entre incrustaciones de libros y bioinformática . [7]
Definiciones
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 reverso del libro, junto con una colección de uno o más medios planos , llamados páginas u hojas del libro, [9] cada uno con el la columna vertebral como su límite. Los libros con un número finito de páginas se pueden incrustar en un espacio tridimensional, por ejemplo, eligiendo ℓ para que sea el eje z de un sistema de coordenadas cartesianas y eligiendo las páginas para que sean los k semiplanos cuyo ángulo diedro con respecto a la xz -plane es un múltiplo entero de 2 π / k . [10]
Un dibujo de libro de un gráfico finito G sobre un libro B es un dibujo de G sobre B de manera 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 un una sola página de B . El número de cruce de libros de k páginas de G es el número mínimo de cruces en un dibujo de libro de k páginas. [11]
Un libro incrustación de G a B es un libro de dibujo que forma un gráfico de la incorporación de G en B . Es decir, es un dibujo de libro de G sobre B que no tiene cruces de bordes. Cada gráfico finito tiene un libro incrustado en un libro con un número suficientemente grande de páginas. Por ejemplo, siempre es posible incrustar cada borde del gráfico en su propia página separada. El grosor del libro , número de página , o número de pila de G es el número mínimo de páginas necesarias para la incorporación de un libro de G . Otro parámetro que mide la calidad de la incrustación de un libro, más allá de su número de páginas, es su ancho de página . Este es el número máximo de bordes que puede atravesar un rayo perpendicular al lomo en 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 extremos de los bordes se cruzan entre sí. . [12] [13] [14]
Es crucial para estas definiciones que los bordes solo puedan permanecer dentro de una sola página del libro. Como ya observó Atneosen, si los bordes pueden pasar de una página a otra a lo largo del lomo del libro, entonces cada gráfico puede integrarse en un libro de tres páginas. [15] [2] [16] Para una incrustación de libro topológico de tres páginas en la que se permiten los cruces de lomo, cada gráfico se puede incrustar con como máximo un número logarítmico de cruces de lomo por borde, [15] y algunos gráficos necesitan esto muchos cruces de la columna vertebral. [17]
Gráficos específicos
Como se muestra en la primera figura, el grosor del libro del gráfico completo K 5 es tres: como gráfico no plano, el grosor del libro es mayor que dos, pero existe un libro incrustado con tres páginas. De manera más general, el grosor del libro de cada gráfico completo con n ≥ 4 vértices es exactamente. Este resultado también proporciona un límite superior en el grosor de libro máximo posible de cualquier gráfico de n -vértices. [10]
El número de cruce de dos páginas del gráfico completo K n es
coincidiendo con una conjetura aún no probada de Anthony Hill sobre cuál debería ser el número de cruce 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 gráfico bipartito completo K a , b es como máximo min ( a , b ) . Para construir un dibujo con este grosor de libro, para cada vértice del lado más pequeño de la bipartición, se pueden colocar los bordes incidentes con ese vértice en su propia página. Este límite no siempre es estrecho; por ejemplo, K 4,4 tiene un grosor de libro de tres, no de cuatro. Sin embargo, cuando los dos lados del gráfico 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 se intercala entre
y cuando r es impar, el límite superior se puede mejorar para
- [10] [20]
El grosor del libro de los gráficos binarios de Bruijn , los gráficos de intercambio aleatorio y los ciclos conectados por cubos (cuando estos gráficos son lo suficientemente grandes como para no ser planos) es exactamente tres. [21]
Propiedades
Planaridad y planaridad exterior
El grosor del libro de un gráfico G dado es como máximo uno si y solo si G es un gráfico plano exterior . Un gráfico plano exterior es un gráfico que tiene una incrustación plana en la que todos los vértices pertenecen a la cara exterior de la incrustación. Para un gráfico de este tipo, colocar los vértices en el mismo orden a lo largo del lomo en el que aparecen en la cara exterior proporciona una incrustación de libro de una página del gráfico dado. (Un punto de articulación del gráfico aparecerá necesariamente más de una vez en el orden cíclico de los vértices alrededor de la cara exterior, pero solo una de esas copias debe incluirse en la incrustación del libro). A la inversa, una incrustación de un libro de una página es automáticamente una incrustación en el plano exterior. Porque, si un gráfico está incrustado en una sola página y otro semiplano se adjunta al lomo para extender su página a un plano completo, entonces la cara exterior de la incrustación incluye todo el semiplano agregado y todos los vértices se encuentran en esta cara exterior. [10] [12]
Cada incrustación de un libro de dos páginas es un caso especial de incrustación plana, porque la unión de dos páginas de un libro es un espacio topológicamente equivalente a todo el plano. Por lo tanto, cada gráfico con un grosor de libro dos es automáticamente un gráfico 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 subgráfico de un gráfico plano que tiene un ciclo hamiltoniano . [10] Si a un gráfico se le da una incrustación de dos páginas, se puede aumentar a un gráfico hamiltoniano plano agregando (en cualquier página) bordes adicionales entre dos vértices consecutivos a lo largo de la columna que aún no son adyacentes, y entre el primero y vértices de la última columna vertebral. El gráfico de Goldner-Harary proporciona 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 no es posible agregarle aristas conservando la planaridad y no tiene un ciclo hamiltoniano . [10] Debido a esta caracterización por ciclos hamiltonianos, los gráficos que tienen incrustaciones de libros de dos páginas también se conocen como gráficos subhamiltonianos . [12]
Todos los gráficos planos cuyo grado máximo sea como máximo cuatro tienen un grosor de libro como máximo dos. [22] Los árboles planos 3 tienen un grosor de libro como máximo de tres. [23] De manera más general, todos los gráficos planos tienen un grosor de libro de cuatro. [5] [6] [24] Mihalis Yannakakis ha afirmado en 1986 [6] que existen algunos gráficos planos que tienen un grosor de libro exactamente cuatro. Sin embargo, una prueba detallada de esta afirmación, anunciada en un artículo de revista posterior, [5] no se conoció hasta 2020, cuando Bekos et al. [24] presentó gráficos planos con un ancho de árbol 4 que requieren cuatro páginas en cualquier libro incrustado.
Comportamiento bajo subdivisiones
¿Puede el grosor del libro de un gráfico estar delimitado por una función del grosor del libro de su subdivisión?
Subdividir cada borde de un gráfico en trazados de dos bordes, agregando nuevos vértices dentro de cada borde, a veces puede aumentar el grosor del libro. Por ejemplo, el gráfico de diamante tiene un grosor de libro uno (es plano exterior) pero su subdivisión tiene un grosor de libro dos (es plano y subhamiltoniano pero no plano exterior). Sin embargo, este proceso de subdivisión a veces también puede reducir significativamente el grosor del libro del gráfico subdividido. Por ejemplo, el grosor del libro del grafo completo K n es proporcional a su número de vértices, pero subdividir cada uno de sus bordes en una ruta de dos bordes produce una subdivisión cuyo grosor del libro es mucho menor, solo que. [25] A pesar de la existencia de ejemplos como éste, Blankenship & Oporowski (1999) conjeturaron que el grosor del libro de una subdivisión no puede ser mucho menor que el del gráfico original. Específicamente, conjeturaron que existe una función f tal que, para cada gráfico G y para el gráfico H formado al reemplazar cada borde en G por un camino de dos bordes, si el grosor del libro de H es t, entonces el grosor del libro de G es como máximo f ( t ) . [16] A partir de 2013, la conjetura de Blankenship-Oporowski sigue sin probarse. [26]
Relación con otros invariantes gráficos
El grosor del libro está relacionado con el grosor , el número de gráficos planos necesarios para cubrir los bordes del gráfico dado. Un gráfico G tiene grosor θ si se puede dibujar en el plano, y sus bordes coloreados con θ colores, de tal manera que los bordes del mismo color no se crucen. De manera análoga, un gráfico G tiene grosor de libro θ si se puede dibujar en un semiplano , con sus vértices en el límite del semiplano, con sus bordes coloreados con θ colores sin cruce entre dos bordes del mismo color. En esta formulación de grosor de libro, los colores de los bordes corresponden a las páginas del libro incrustado. Sin embargo, el grosor y el grosor del libro pueden ser muy diferentes entre sí: existen gráficos ( subdivisiones de gráficos completos ) que tienen un grosor de libro ilimitado, [25] [15] [16] a pesar de tener un grosor dos. [25]
Las gráficas de ancho de árbol k tienen un grosor de libro como máximo k + 1 [27] [28] y este límite es estrecho para k > 2 . [27] Los gráficos con m bordes tienen un grosor de libro., [29] y los gráficos del género g tienen un grosor de libro. [30] De manera más general, cada familia de gráficos cerrados menores tiene un grosor de libro acotado. [31] [32] Por otro lado, los gráficos de 1 plano , que no están cerrados en menores, [31] también tienen el grosor del libro delimitado, [33] pero algunos gráficos de 1 plano que incluyen K 2,2,2, 2 tienen un grosor de libro de al menos cuatro. [34]
Cada menor superficial de un gráfico de grosor de libro acotado es un gráfico disperso , cuya relación de aristas a vértices está acotada por una constante que depende únicamente de la profundidad del menor y del grosor del libro. Es decir, en la terminología de Nešetřil & Ossona de Mendez (2012) , las gráficas de espesor de libro acotado tienen expansión acotada . [31] Sin embargo, incluso los gráficos de grado acotado , un requisito mucho más estricto que tener expansión acotada, pueden tener un grosor de libro ilimitado. [35]
Debido a que las gráficas de espesor de libro dos son gráficas planas, obedecen al teorema del separador planar : tienen separadores, subconjuntos de vértices cuya eliminación divide la gráfica en partes con un máximo de 2 n / 3 vértices cada una, con solovértices en el separador. Aquí, n se refiere al número de vértices en el gráfico. Sin embargo, existen gráficos de libro de espesor tres que no tienen separadores de tamaño sublineal. [36]
Los bordes dentro de una sola página de un libro incrustado se comportan de alguna manera como una estructura de datos de pila . Esto se puede formalizar considerando una secuencia arbitraria de operaciones push y pop en una pila, y formando un gráfico en el que las operaciones de la pila corresponden a los vértices del gráfico, colocados en orden secuencial a lo largo del lomo de un libro incrustado. Luego, si se dibuja un borde de cada operación emergente que saca un objeto x de la pila, a la operación push anterior que empujó x , el gráfico resultante tendrá automáticamente una incrustación de una página. Por esta razón, el número de página de un gráfico también se ha denominado número de pila . De la misma manera, se puede considerar una secuencia arbitraria de operaciones de poner y quitar de cola 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 uno. enqueue operación y la correspondiente dequeue. Luego, en este gráfico, cada dos bordes se cruzarán o cubrirán intervalos disjuntos en la columna. Por analogía, los investigadores han definido una inserción en cola de un gráfico para que sea una inserción en un libro topológico, de modo que cada vértice se encuentra en el lomo, cada borde se encuentra en una sola página y cada dos bordes en la misma página se cruzan o cubren separados. intervalos en la columna vertebral. El número mínimo de páginas necesarias para la incorporación de una cola de un gráfico se denomina número de cola . [31] [37] [38]
Complejidad computacional
Encontrar el grosor del libro de una gráfica es NP-difícil . Esto se deriva del hecho de que encontrar ciclos hamiltonianos en gráficos planos máximos es NP-completo . En un gráfico plano máximo, el grosor del libro es dos si y solo si existe un ciclo hamiltoniano. Por lo tanto, también es NP-completo probar si el grosor del libro de un gráfico plano máximo dado es dos. [39]
Si un orden de los vértices de un gráfico a lo largo del lomo 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 una gráfica formada aumentando el valor dado. grafica con un ciclo que conecta los vértices en su orden de la columna vertebral. [7] Unger (1992) afirmó que la búsqueda de incrustaciones de tres páginas con un orden fijo en el lomo también se puede realizar en tiempo polinomial, aunque su redacción de este resultado omite muchos detalles. [40] Sin embargo, para gráficos que requieren cuatro o más páginas, el problema de encontrar una incrustación con el mínimo número posible de páginas sigue siendo NP-hard, a través de una equivalencia al problema NP-hard de colorear gráficos circulares , los gráficos de intersección de acordes de un círculo . Dado un gráfico G con un ordenamiento columna fija por sus vértices, dibujo estos vértices en el mismo orden alrededor de un círculo y el dibujo de los bordes de G como segmentos de línea produce una colección de acordes que representan G . Luego, se puede formar un gráfico circular que tenga las cuerdas de este diagrama como vértices y pares de cuerdas cruzadas como aristas. Una coloración del gráfico circular representa una partición de los bordes de G en subconjuntos que se pueden dibujar sin cruzar en una sola página. Por lo tanto, una coloración óptima equivale a una incrustación óptima del libro. Dado que colorear gráficos circulares con cuatro o más colores es NP-difícil, y dado que cualquier gráfico circular puede formarse 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-difícil. [41] [42] [43] Para un orden de vértice fijo en el lomo de un dibujo de libro de dos páginas, también es NP-difícil minimizar el número de cruces cuando este número es distinto de cero. [42]
Si se desconoce el orden del lomo pero se proporciona una partición de los bordes en dos páginas, entonces es posible encontrar una incrustación de 2 páginas (si existe) en tiempo lineal mediante un algoritmo basado en árboles SPQR . [44] [45] 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 del borde. Encontrar el número de cruce de libros de un gráfico 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 del isomorfismo del subgrafo , de encontrar si un gráfico de patrón de tamaño acotado existe como un subgrafo de un gráfico más grande, se puede resolver en tiempo lineal cuando el gráfico más grande tiene un grosor de libro acotado. Lo mismo es cierto para detectar si el gráfico de patrón es un subgráfico inducido del gráfico más grande, o si tiene un homomorfismo de gráfico con el gráfico más grande. [46] [47] Por la misma razón, el problema de probar si una gráfica de espesor de libro acotado obedece a una fórmula dada de lógica de primer orden es tratable con parámetros fijos . [48]
Bekos, Kaufmann & Zielke (2015) describen un sistema para encontrar incrustaciones óptimas de libros transformando el problema en una instancia del problema de satisfacibilidad booleano y aplicando un solucionador SAT al problema resultante. Afirman que su sistema es capaz de encontrar una incrustación óptima para gráficos planos máximos de 400 vértices en aproximadamente 20 minutos. [34]
Aplicaciones
Multiprocesamiento tolerante a fallas
Una de las principales motivaciones para estudiar la incrustación de libros citada por Chung, Leighton y Rosenberg (1987) involucra una aplicación en el diseño de VLSI , a la organización de multiprocesadores tolerantes a fallas . En el sistema DIOGENES desarrollado por estos autores, las CPU de un sistema multiprocesador están ordenadas en una secuencia lógica correspondiente al lomo de un libro (aunque esta secuencia no necesariamente se ubica a lo largo de una línea en el diseño físico de este sistema). Los enlaces de comunicación que conectan estos procesadores se agrupan en "paquetes" que corresponden a las páginas de un libro y actúan como pilas : conectar uno de los procesadores al inicio de un nuevo enlace de comunicaciones empuja todos los enlaces anteriores hacia arriba en el paquete y conecta otro El procesador al final de un enlace de comunicación lo conecta con el que está en la parte inferior del paquete y abre todos los demás. Debido a este comportamiento de pila, un solo paquete puede manejar un conjunto de enlaces de comunicaciones que forman los bordes de una sola página en un libro incrustado. 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 averiado, siempre que queden suficientes procesadores sin fallas para implementar la red. Las topologías de red que puede implementar este sistema son exactamente las que tienen un grosor de libro como máximo igual al número de paquetes que se han puesto a disposición. [39] La incrustación de libros también se puede utilizar para modelar la ubicación de los cables que conectan los componentes VLSI en las capas de un circuito. [49]
Clasificación de pilas
Otra aplicación citada por Chung, Leighton y Rosenberg (1987) se refiere a la clasificación de permutaciones utilizando pilas . Un resultado influyente de Donald Knuth ( 1968 ) mostró que un sistema que procesa un flujo de datos empujando elementos entrantes a una pila y luego, en momentos elegidos apropiadamente, sacándolos de la pila a un flujo de salida puede ordenar los datos si y solo si su orden inicial se describe mediante una permutación que evita el patrón de permutación 231. [50] Desde entonces, se ha trabajado mucho en problemas similares de clasificación de flujos de datos 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 insertarse en una de varias pilas. Luego, una vez que todos los datos se han enviado de esta manera, los elementos se extraen de estas pilas (en el orden apropiado) a un flujo de salida. Como Chung et al. Observemos, una permutación dada puede ser ordenada por este sistema si y solo si una determinada gráfica, derivada de la permutación, tiene un libro incrustado con los vértices en un cierto orden fijo a lo largo del lomo y con un número de páginas que sea como máximo igual al número de pilas. [39]
Control de trafico
Como describió Kainen (1990) , la inclusión de un libro se puede utilizar para describir las fases de una señal de tráfico 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 los carriles para bicicletas, así como los carriles para vehículos motorizados) pueden representarse como los vértices de un gráfico, colocados en el lomo de un libro incrustado en el sentido de las agujas del reloj. orden alrededor del cruce. Los caminos a través de la intersección que toma el tráfico para pasar de 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 de un carril de tráfico entrante a uno saliente que pertenecen al mismo segmento de la carretera, lo que representa un giro en U de ese segmento a ese segmento, solo si los giros en U están permitidos en el unión. Para un subconjunto dado de estos bordes, el subconjunto representa una colección de caminos que se pueden atravesar 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 un libro incrustado. Por lo tanto, un libro incrustado de este gráfico describe una partición de las rutas en subconjuntos que no interfieren, y el grosor del libro de este gráfico (con su incrustación fija en el lomo) da el número mínimo de fases distintas necesarias para un programa de señalización que incluye todas las posibles rutas de tráfico a través del cruce. [51]
Dibujo gráfico
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 , diagramas de arco [52] y diseños circulares, [53] pueden verse como incrustaciones de libros, y la incrustación de libros también se ha aplicado en la construcción de diseños agrupados, [44] incrustaciones simultáneas, [54 ] y dibujos de gráficos tridimensionales. [55]
Un diagrama de arco [52] o incrustación lineal [42] 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, lo que a veces también permite dibujar bordes en segmentos de la línea. Este estilo de dibujo corresponde a un libro incrustado con una página (si todos los semicírculos están por encima de la línea) o dos páginas (si se usan ambos lados de la línea), y se introdujo originalmente como una forma de estudiar los números cruzados de gráficos. [56] [57] Los gráficos planos que no tienen incrustaciones de libros de dos páginas también se pueden dibujar de manera similar, permitiendo que sus bordes se representen mediante múltiples semicírculos por encima y por debajo de la línea. Tal dibujo no es un libro incrustado según la definición habitual, sino que se ha denominado incrustación de libro topológico . [58] Para cada gráfico plano, siempre es posible encontrar una incrustación en la que cada borde cruza la columna como máximo una vez. [59]
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. [53] Una vez más, una ubicació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 ubicación tanto dentro como fuera del círculo corresponde a un dibujo de libro de dos páginas. [60]
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 , [42] pero puede aproximarse con una relación de aproximación de O (log 2 n ) donde n es el número de vértices. [61] Minimizar el número de cruce de una página o dos páginas se puede tratar 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 cruce y el ancho del árbol del gráfico. [62] [63] También se han ideado métodos heurísticos para reducir la complejidad del cruce, basados, por ejemplo, en un orden de inserción de vértices cuidadoso y en la optimización local . [53]
Las incrustaciones de libros de dos páginas con una partición fija de los bordes en las páginas se pueden interpretar como una forma de planaridad agrupada , en la que el gráfico dado debe dibujarse de tal manera que se coloquen partes del gráfico (los dos subconjuntos de bordes). en el dibujo de una manera que refleje su agrupación. [44] La incrustación de libros de dos páginas también se ha utilizado para encontrar incrustaciones simultáneas de gráficos, en los que se dan dos gráficos en el mismo conjunto de vértices y se debe encontrar una ubicación para los vértices en los que ambos gráficos se dibujan planamente con bordes rectos. [54]
También se han utilizado incrustaciones de libros con más de dos páginas para construir dibujos tridimensionales de gráficos. En particular, Wood (2002) utilizó una construcción para incrustaciones de libros que mantiene bajo el grado de cada vértice dentro de cada página, como parte de un método para incrustar gráficos en una cuadrícula tridimensional de bajo volumen. [55]
Plegamiento de ARN
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 del ácido nucleico se puede describir esquemáticamente como una cadena de bases (la secuencia de ARN en sí), dibujada a lo largo de una línea, junto con una colección de arcos por encima de la línea que describe los pares base de la estructura. Es decir, aunque estas estructuras en realidad tienen una forma tridimensional complicada, su conectividad (cuando existe una estructura secundaria) puede describirse mediante una estructura más abstracta, una incrustación de 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 llamada "estructura bisecundaria " para ciertos pseudonudos de ARN que toma la forma de un libro de dos páginas incrustado: la secuencia de ARN se dibuja nuevamente a lo largo de una línea, pero los pares de bases se dibujan como arcos tanto por encima como por debajo de esta línea. Para formar una estructura bisecundaria, un gráfico debe tener un grado máximo como máximo de tres: cada base solo puede participar en un arco del diagrama, además de los dos enlaces a sus vecinos en la secuencia de bases. Las ventajas de esta formulación incluyen el hecho de que excluye 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, probar la existencia de una estructura bisecundaria para un par de bases dado es sencillo. El problema de asignar aristas a las dos páginas de una manera compatible se puede formular como una instancia de satisfacibilidad 2 , o como un problema de probar la bipartita del grafo circular cuyos vértices son los pares de bases y cuyas aristas describen cruces entre pares de bases. [7] Alternativamente y de manera más eficiente, como muestran Haslinger y Stadler (1999) , existe una estructura bisecundaria si y solo si el gráfico del diagrama de la entrada (un gráfico formado conectando las bases en un ciclo en su orden de secuencia y agregando los pares de bases dados como aristas) es un gráfico plano . [7] Esta caracterización permite que las estructuras bi-secundarias sean reconocidas en tiempo lineal como una instancia de prueba de planaridad .
Blin y col. (2007) utilizaron la conexión entre estructuras secundarias e incrustaciones de libros como parte de una prueba de la dureza NP de ciertos problemas en la comparación de estructuras secundarias de ARN. [64] Y si una estructura de ARN es terciaria en lugar de bi-secundaria (es decir, si requiere más de dos páginas en su diagrama), entonces determinar el número de página es nuevamente NP-difícil. [sesenta y cinco]
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 accesibilidad en grafos dirigidos . Como han observado, la accesibilidad para gráficos 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 polinómico inequívoco). Sin embargo, la accesibilidad para gráficos dirigidos de tres páginas requiere todo el poder del espacio logarítmico no determinista . Por lo tanto, las incrustaciones de libros parecen estar íntimamente relacionadas con la distinción entre estas dos clases de complejidad. [66]
La existencia de gráficos expansores con número de página constante [36] es el paso clave para demostrar que no existe una simulación de tiempo subcuadrático de máquinas de Turing no deterministas de dos cintas mediante máquinas de Turing no deterministas de una cinta. [67]
Otras áreas de las matemáticas
McKenzie y Overbay (2010) estudian aplicaciones del grosor de libros en álgebra abstracta , utilizando gráficas definidas a partir de los divisores cero de un anillo local finito haciendo un vértice para cada divisor cero y una arista para cada par de valores cuyo producto es cero. [68]
En una secuencia de varios papeles, Dynnikov ha estudiado las incrustaciones de nudos y enlaces en libros topológicos , mostrando que estas incrustaciones pueden describirse mediante una secuencia combinatoria de símbolos y que la equivalencia topológica de dos enlaces se puede demostrar mediante una secuencia de cambios locales en las incrustaciones. [69] [70]
Referencias
- ^ a b Persinger, CA (1966), "Subconjuntos de n- libros en E 3 ", Pacific Journal of Mathematics , 18 : 169-173, doi : 10.2140 / pjm.1966.18.169 , MR 0195077.
- ^ a b Atneosen, Gail Adele (1968), Sobre la incrustabilidad de compacta en n -books: propiedades intrínsecas y extrínsecas , Ph.D. tesis, Universidad Estatal de Michigan , pág. 79, MR 2617705. Ver también Atneosen, Gail H. (1972), " Continuos unidimensionales de hojas n " (PDF) , Fundamenta Mathematicae , 74 (1): 43–45, doi : 10.4064 / fm-74-1-43-45 , MR 0293592.
- ^ Kainen, Paul C. (1974), "Algunos resultados recientes en la 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 Gráficos y Combinatoria en la Universidad George Washington del 18 al 22 de junio de 1973) , Lecture Notes in Mathematics, 406 , págs. 76-108.
- ^ Ollmann, L. Taylor (1973), "Sobre el grosor del libro de varios gráficos", en Hoffman, Frederick; Levow, Roy B .; Thomas, Robert SD (eds.), Proc. IV Conferencia del Sureste sobre Combinatoria, Teoría de Grafos y Computación , Congressus Numerantium, VIII , p. 459.
- ^ a b c Yannakakis, Mihalis (1989), "Incrustar gráficos planos en cuatro páginas", Journal of Computer and System Sciences , 38 : 36–67, doi : 10.1016 / 0022-0000 (89) 90032-9
- ^ a b c Yannakakis, Mihalis (1986), "Cuatro páginas son necesarias y suficientes para gráficos planos", Actas del 18º Simposio ACM sobre Teoría de la Computación (STOC '86) , págs. 104–108, doi : 10.1145 / 12130.12141 , ISBN 0-89791-193-8, S2CID 5359519.
- ^ a b c d e Haslinger, Christian; Stadler, Peter F. (1999), "Estructuras de ARN con pseudo-nudos: propiedades gráficas teóricas, combinatorias y estadísticas", Bulletin of Mathematical Biology , 61 (3): 437–467, doi : 10.1006 / bulm.1998.0085 , PMC 7197269 , PMID 17883226.
- ^ Hales, TC (1997), " Empaquetaduras de esferas . II", Geometría discreta y computacional , 18 (2): 135-149, doi : 10.1007 / PL00009312 , MR 1455511.
- ^ La terminología de "columna vertebral" y "páginas" es más estándar en los enfoques teóricos de gráficos modernos del tema. Para la terminología "atrás" y "hojas", véase Persinger (1966) .
- ^ a b c d e f g Bernhart, Frank R .; Kainen, Paul C. (1979), "El grosor del libro de un gráfico", Journal of Combinatorial Theory , Serie B, 27 (3): 320–331, doi : 10.1016 / 0095-8956 (79) 90021-2 , MR 0554297.
- ^ Shahrokhi, Farhad; Székely, László A .; Sýkora, Ondrej; Vrťo, Imrich (1996), "The book crossing number of a graph", Journal of Graph Theory , 21 (4): 413–424, doi : 10.1002 / (SICI) 1097-0118 (199604) 21: 4 <413: : AID-JGT7> 3.3.CO; 2-5 , MR 1377615.
- ^ a b c Heath, Lenwood S. (1987), "Incorporación de gráficos planos externos en libros pequeños", SIAM Journal on Algebraic and Discrete Methods , 8 (2): 198-218, doi : 10.1137 / 0608018 , MR 0881181.
- ^ 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.
- ^ Stöhr, Elena (1991), "The pagewidth of trivalent planar graphs", Discrete Mathematics , 89 (1): 43–49, doi : 10.1016 / 0012-365X (91) 90398-L , MR 1108073.
- ^ a b c Enomoto, Hikoe; Miyauchi, Miki Shimabara (1999), "Incrustar gráficos en un libro de tres páginas con O ( M log N ) cruces de bordes sobre el lomo", SIAM Journal on Discrete Mathematics , 12 (3): 337–341, doi : 10.1137 / S0895480195280319 , MR 1710241.
- ^ a b c Blankenship, Robin; Oporowski, Bogdan (1999), Subdivisiones de dibujo de gráficos bipartitos completos y completos en libros , Informe técnico 1999-4, Departamento de Matemáticas, Universidad Estatal de Luisiana, CiteSeerX 10.1.1.36.4358.
- ^ Enomoto, Hikoe; Miyauchi, Miki Shimabara; Ota, Katsuhiro (1999), "Límites inferiores para el número de cruces de bordes sobre el lomo en un libro topológico incrustado de un gráfico", Discrete Applied Mathematics , 92 (2-3): 149-155, doi : 10.1016 / S0166 -218X (99) 00044-X , MR 1697548.
- ^ Á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 ampliado)", 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.
- ^ 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 gráficos bipartitos completos", Matemáticas aplicadas discretas , 167 : 80–93, arXiv : 1210.2918 , doi : 10.1016 / j.dam.2013.11.001 , MR 3166108 , S2CID 40920263.
- ^ Sperfeld, Konrad (2013), "En el número de página de gráficos completos de partitos impares", Discrete Mathematics , 313 (17): 1689–1696, doi : 10.1016 / j.disc.2013.04.028 , MR 3061004.
- ^ Hasunuma, Toru; Shibata, Yukio (1997), "Embedding de Bruijn, Kautz and shuffle-exchange networks in books", 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áginas de los ciclos conectados al cubo", Matemáticas en Ciencias de la Computación , 3 (1): 109-117, doi : 10.1007 / s11786-009-0012-y , MR 2596254 , S2CID 11830437. Ver también Obrenić, Bojana (1993), "Embedding de Bruijn and shuffle-exchange graphs in five pages", SIAM Journal on Discrete Mathematics , 6 (4): 642–654, doi : 10.1137 / 0406049 , MR 1241401.
- ^ Bekos, Michael A .; Gronemann, Martin; Raftopoulou, Chrysanthi N. (2014), "Incrustaciones de libros de dos páginas de gráficos de 4 planos", Actas del 31º Simposio sobre aspectos teóricos de la informática , págs. 137-148, arXiv : 1401.0684 , doi : 10.4230 / LIPIcs. STACS.2014.137.
- ^ Heath, Lenny (1984), "Incrustar gráficas planas en siete páginas", Actas del 25º Simposio anual sobre los fundamentos de la informática , págs. 74–83, doi : 10.1109 / SFCS.1984.715903.
- ^ a b Bekos, Michael A .; Kaufmann, Micheal; Klute, Fabián; Pupyrev, Sergey; Raftopoulou, Chrysanthi; Ueckerdt, Torsten (2020), Cuatro páginas son realmente necesarias para gráficos planar , arXiv : 2004.07630.
- ^ a b c Eppstein, David (2001), Separando el grosor geométrico del grosor del libro , arXiv : math.CO/0109195 , Bibcode : 2001math ...... 9195E.
- ^ Madera, David (19 de enero de 2009), "Libro Espesor de subdivisiones" , abierto Problema Jardín , recuperada 02/05/2013.
- ^ a b Dujmović, Vida; Wood, David R. (2007), "Graph treewidth and geometric thick parameters", Geometría discreta y computacional , 37 (4): 641–670, arXiv : math / 0503553 , doi : 10.1007 / s00454-007-1318-7 , S2CID 9141367.
- ^ Ganley, Joseph L .; Heath, Lenwood S. (2001), "El número de páginas de k -árboles es O ( k ) ", Matemáticas aplicadas discretas , 109 (3): 215-221, doi : 10.1016 / S0166-218X (00) 00178-5 , Señor 1818238.
- ^ Malitz, Seth M. (1994), "Los gráficos con bordes E tienen número de página O (√ E ) ", Journal of Algorithms , 17 (1): 71–84, doi : 10.1006 / jagm.1994.1027 , MR 1279269.
- ^ Malitz, Seth M. (1994), "Los gráficos de 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.
- ^ a b c d Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms , Algorithms and Combinatorics, 28 , Springer, pp. 321–328, doi : 10.1007 / 978-3-642-27875-4 , ISBN 978-3-642-27874-7, MR 2920058.
- ^ Blankenship, R. (2003), Embeddings of Graphs de libros , Ph.D. tesis, Departamento de Matemáticas, Universidad Estatal de Louisiana. Según lo citado por Nešetřil y Ossona de Mendez (2012) .
- ^ Bekos, Michael A .; Bruckdorfer, Till; Kaufmann, Michael; Raftopoulou, Chrysanthi (2015), "Los gráficos 1-planar tienen un grosor de libro constante", Algoritmos - ESA 2015 , Lecture Notes in Computer Science, 9294 , Springer, págs. 130-141, doi : 10.1007 / 978-3-662-48350 -3_12.
- ^ a b Bekos, Michael; Kaufmann, Michael; Zielke, Christian (2015), "El libro que integra el problema 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.
- ^ Barát, János; Matoušek, Jiří ; Wood, David R. (2006), "Los gráficos de grados acotados tienen un grosor geométrico arbitrariamente grande", Electronic Journal of Combinatorics , 13 (1): R3, doi : 10.37236 / 1029 , MR 2200531.
- ^ a b Dujmović, Vida; Sidiropoulos, Anastasios; Madera, David R. (2015), 3-Monótono expansores , arXiv : 1501.05020 , bibcode : 2015arXiv150105020D, mejorando un resultado anterior que muestra la existencia de expansores con número de página constante desde 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 SL 2 (ℝ) 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. Ver también Galil, Zvi ; Kannan, Ravi ; Szemerédi, Endre (1989), "On 3-pushdown graphs with large separators", Combinatorica , 9 (1): 9-19, doi : 10.1007 / BF02122679 , MR 1010295 , S2CID 37506294; Dvir, Zeev; Wigderson, Avi (2010), "Expansores monótonos: construcciones y aplicaciones", Teoría de la Computación , 6 : 291–308, doi : 10.4086 / toc.2010.v006a012 , MR 2770077.
- ^ Heath, Lenwood S .; Rosenberg, Arnold L. (1992), "Trazado de gráficos mediante colas", SIAM Journal on Computing , 21 (5): 927–958, doi : 10.1137 / 0221055 , MR 1181408.
- ^ Dujmović, Vida; Wood, David R. (2004), "Sobre diseños lineales de gráficos", Matemáticas discretas e informática teórica , 6 (2): 339–357, MR 2081479.
- ^ a b c Chung, Fan RK ; Leighton, Frank Thompson ; Rosenberg, Arnold L. (1987), "Incrustar gráficos en libros: un problema de diseño con aplicaciones al diseño VLSI" (PDF) , SIAM Journal on Algebraic and Discrete Methods , 8 (1): 33–58, doi : 10.1137 / 0608002.
- ^ Unger, Walter (1992), "La complejidad de colorear gráficos circulares", STACS 92: Noveno Simposio anual sobre aspectos teóricos de la informática, Cachan, Francia, 13-15 de febrero de 1992, Actas , Lecture Notes in Computer Science, 577 , Berlín: Springer, págs. 389–400, doi : 10.1007 / 3-540-55210-3_199.
- ^ Unger, Walter (1988), "Sobre la coloración k de los gráficos circulares", Actas del 5º Simposio sobre aspectos teóricos de la informática (STACS '88) , Lecture Notes in Computer Science, 294 , Springer-Verlag, págs. 61–72, doi : 10.1007 / BFb0035832.
- ^ a b c d Masuda, Sumio; Nakajima, Kazuo; Kashiwabara, Toshinobu; Fujisawa, Toshio (1990), "Crossing minimization in linear embeddings of graphs", IEEE Transactions on Computers , 39 (1): 124-127, doi : 10.1109 / 12.46286 , MR 1032144.
- ^ Garey, MR ; Johnson, DS ; Miller, GL ; Papadimitriou, CH (1980), "La complejidad de colorear arcos circulares y acordes", SIAM Journal on Algebraic and Discrete Methods , 1 (2): 216-227, doi : 10.1137 / 0601025 , MR 0578325.
- ^ a b c Hong, Seok-Hee; Nagamochi, Hiroshi (2009), Incrustación de libros de dos páginas y planaridad de gráficos agrupados (PDF) , Informe técnico (2009-004 ed.), Departamento de Física y Matemáticas Aplicadas, Universidad de Kyoto, Japón.
- ^ Angelini, Patrizio; Di Bartolomeo, Marco; Di Battista, Giuseppe (2013), "Implementación de un algoritmo de prueba de inclusión de libro dividido de 2 páginas", Dibujo gráfico: 20 ° Simposio Internacional, GD 2012, Redmond, WA, EE. UU., 19 al 21 de septiembre de 2012, Artículos seleccionados revisados , Notas de conferencias en Ciencias de la Computación, 7704 , Springer, págs. 79–89, arXiv : 1209.0598 , doi : 10.1007 / 978-3-642-36763-2_8 , MR 3067219 , S2CID 15360191.
- ^ Nešetřil y Ossona de Mendez (2012) , Corolario 18.1, p. 401.
- ^ Nešetřil, Jaroslav ; Ossona de Méndez, Patrice (2008), "Grad 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 2.397.336 , S2CID 1139740.
- ^ Nešetřil y Ossona de Mendez (2012) , Teorema 18.7, p. 405.
- ^ Rosenberg, Arnold L. (1986), "Book embeddings and wafer-scale integration", Actas de la decimoséptima conferencia internacional del sureste sobre combinatoria, teoría de grafos y computación (Boca Raton, Florida, 1986) , Congressus Numerantium, 54 , págs. 217–224, MR 0885282.
- ^ 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.
- ^ Kainen, Paul C. (1990), "El grosor del libro de un gráfico. II", Actas de la Vigésima Conferencia Sureste sobre Combinatoria, Teoría de Gráficos y Computación (Boca Raton, FL, 1989) , Congressus Numerantium, 71 , págs. 127-132, MR 1041623.
- ^ a b Wattenberg, M. (2002), "Diagramas de arco: visualización de la estructura en cuerdas", Actas del Simposio de IEEE sobre visualización de información (INFOVIS 2002) , págs. 110-116, doi : 10.1109 / INFVIS.2002.1173155 , S2CID 881989.
- ^ a b c Baur, Michael; Brandes, Ulrik (2005), "Crossing reducción 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, 2004, Revised Papers , Lecture Notes in Computer Science, 3353 , Springer, págs. 332–343, doi : 10.1007 / 978-3-540-30559-0_28.
- ^ a b 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 biconectado o conectado", Journal of Discrete Algorithms , 14 : 150-172, doi : 10.1016 / j.jda.2011.12.015 , MR 2922068.
- ^ a b Wood, David R. (2002), "Embeddings de libros de grado acotado y dibujo de gráficos ortogonales tridimensionales", Graph Drawing: 9th International Symposium, GD 2001, Vienna, Austria, 23-26 de septiembre de 2001, Revised Papers , Lecture Notes en Ciencias de la Computación, 2265 , Springer, Berlín, págs. 312–327, doi : 10.1007 / 3-540-45848-4_25 , MR 1962433.
- ^ Saaty, Thomas L. (1964), "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 , 52 (3): 688–690, Bibcode : 1964PNAS ... 52 ..688S , doi : 10.1073 / pnas.52.3.688 , MR 0166772 , PMC 300329 , PMID 16591215.
- ^ 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.
- ^ Miyauchi, Miki (2006), "Incrustación de libros topológicos de gráficos bipartitos", Transacciones de IEICE sobre fundamentos de electrónica, comunicaciones y ciencias de la computación , E89-A (5): 1223–1226, Bibcode : 2006IEITF..89.1223M , doi : 10.1093 /ietfec/e89-a.5.1223.
- ^ Giordano, Francesco; Liotta, Giuseppe; Mchedlidze, Tamara; Symvonis, Antonios (2007), "Computing upward topological book embeddings of upward planar digraphs", Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japón, 17-19 de diciembre de 2007, Proceedings , Lecture Notes in Computer Science, 4835 , Springer, págs. 172–183, doi : 10.1007 / 978-3-540-77120-3_17.
- ^ Él, 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.
- ^ Shahrokhi, Farhad; Sýkora, Ondrej; Székely, László A .; Vrt'o, Imrich (1995), "Incrustaciones de libros y números cruzados", Conceptos teóricos de gráficos en ciencias de la computación: 20º Taller internacional, WG '94, Herrsching, Alemania, 16-18 de junio de 1994, Actas , Notas de conferencias en computadora Science, 903 , Springer, págs. 256–268, doi : 10.1007 / 3-540-59071-4_53.
- ^ Bannister, Michael J .; Eppstein, David ; Simons, Joseph A. (2013), "Tractabilidad de parámetro fijo de la minimización de cruces de casi árboles", Dibujo gráfico: 21º Simposio Internacional, GD 2013, Burdeos, Francia, 23 al 25 de septiembre de 2013, Artículos seleccionados revisados , Notas de la conferencia en Ciencias de la computación, 8242 , págs. 340–351, arXiv : 1308.5741 , doi : 10.1007 / 978-3-319-03841-4_30 , S2CID 10142319.
- ^ Bannister, Michael J .; Eppstein, David (2014), "Minimización de cruces para dibujos de gráficos de 1 página y 2 páginas con ancho de árbol acotado", Proc. 22 Int. Symp. Graph Drawing (GD 2014) , Lecture Notes in Computer Science, 8871 , Springer-Verlag, págs. 210–221, arXiv : 1408.6321 , doi : 10.1007 / 978-3-662-45803-7_18 , MR 3333228.
- ^ Blin, Guillaume; Fertin, Guillaume; Rusu, Irena; Sinoquet, Christine (2007), "Extendiendo la dureza de la comparación de estructuras secundarias de ARN", Combinatoria, algoritmos, metodologías probabilísticas y experimentales: primer simposio internacional, ESCAPE 2007, Hangzhou, China, 7-9 de abril de 2007, artículos seleccionados revisados (PDF ) , Lecture Notes in Computer Science, 4614 , págs. 140-151, doi : 10.1007 / 978-3-540-74450-4_13.
- ^ Clote, Peter; Dobrev, Stefan; Dotu, Ivan; Kranakis, Evangelos; Krizanc, Danny; Urrutia, Jorge (2012), "En el número de página de estructuras secundarias de ARN con pseudonudos", Journal of Mathematical Biology , 65 (6–7): 1337–1357, doi : 10.1007 / s00285-011-0493-6 , PMID 22159642 , S2CID 8700502.
- ^ Pavan, A .; Tewari, Raghunath; Vinodchandran, NV (2012), "Sobre el poder de la no ambigü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.
- ^ Galil, Zvi ; Kannan, Ravi ; Szemerédi, Endre (1989), "Sobre separadores no triviales para gráficos de k páginas y simulaciones por máquinas de Turing no deterministas de una sola cinta", Journal of Computer and System Sciences , 38 (1): 134-149, doi : 10.1016 / 0022-0000 (89) 90036-6.
- ^ McKenzie, Thomas; Overbay, Shannon (2010), "Book embeddings and zero divisors", Ars Combinatoria , 95 : 55–63, MR 2656248.
- ^ 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.
- ^ Dynnikov, IA (2001), "Una nueva forma de representar enlaces, formalismo unidimensional y tecnología desenredante", Acta Applicandae Mathematicae , 69 (3): 243-283, doi : 10.1023 / A: 1014299416618 , MR 1885279 , S2CID 116488382.