En teoría de grafos, un embebido en libro es una generalización del embebido plano de un grafo a embebidos en un libro, una colección de semiespacios, todos con la misma recta como límite. Por lo general, se requiere que los vértices del grafo se encuentren en esta línea límite, llamada "columna vertebral", y se requiere que los vínculos permanezcan dentro de un solo semiplano. El espesor del libro de un grafo es el número más pequeño posible de semiplanos para cualquier embebido en libro del grafo. El grosor del libro también se denomina número de páginas, número de pila o grosor exterior fijo. Los embebidos en libro también se han utilizado para definir varios otros invariantes de grafo, incluido el ancho de página y el número de cruces del libro.
Cada grafo con vértices tiene un grosor de libro como máximo de , y esta fórmula proporciona el grosor del libro exacto para un grafo completo. Los grafos con grosor de libro uno son los grafos planos exteriores. Los grafos con grosor de libro como máximo dos se denominan grafos subhamiltonianos, que siempre son planos; de manera más general, cada grafo plano tiene un grosor de libro de cuatro como máximo. Todos los familias de grafos cerrados menores, y en particular los grafos con ancho de árbol acotado o genus acotado, también tienen grosor de libro acotado. Determinar el grosor exacto del libro de un grafo dado, con o sin conocer un orden de vértices fijo en el lomo del libro, es un problema de complejidad NP-hard. Probar la existencia de un libro de tres páginas embebido de un grafo, dado un orden fijo de los vértices en el lomo del libro, tiene una complejidad computacional desconocida: no se sabe que sea resoluble en tiempo polinomial ni que sea de dificultad NP.
Una de las motivaciones originales para estudiar embebidos en libros involucró aplicaciones en el diseño de integración a muy gran escala, proceso en el que los vértices de un embebido en libro representan componentes de un circuito y los cables representan las conexiones entre ellos. Los embebidos en libros también tiene aplicaciones en dibujo de grafos, donde dos de los estilos de visualización estándar para grafos, los diagramas de arcos y el diseño circular, pueden construirse mediante embebidos en libros.
En planificación de transporte, las diferentes fuentes y destinos del tráfico peatonal y vehicular que se encuentran e interactúan en un semáforo se pueden modelar matemáticamente como los vértices de un grafo, con vínculos que conectan diferentes pares de origen y destino. Se puede usar un embebido en libro de este grafo para diseñar un cronograma que permita que todo el tráfico se mueva a través de la intersección con la menor cantidad posible de fases de semáforo. En los problemas de bioinformática que involucran la estructura de plegado del ácido ribonucleico, los embebidos en libro de una sola página representan formas clásicas de la estructura secundaria de un ácido nucleico, y los embebidos en libro de dos páginas representan pseudonudos. Otras aplicaciones de embebidos en libro incluyen el álgebra abstracta y la teoría de nudos.
Historia La noción de libro, como espacio topológico, fue definida por C. A. Persinger y Gail Atneosen en la década de 1960.. See also . Como parte de este trabajo, Atneosen ya consideró embebidos de grafos en libros. Los embebidos que estudió usaban la misma definición que los embebidos de grafos en cualquier otro espacio topológico: los vértices están representados por puntos distintos, los vínculos están representados por curvas y la única forma en que dos vínculos pueden intersecarse es que se encuentren en un punto final común.
A principios de la década de 1970, Paul C. Kainen y L. Taylor Ollmann desarrollaron un tipo de embebido más restringido que se utilizó en la mayoría de las investigaciones posteriores. En su formulación, los vértices del grafo deben colocarse en el lomo del libro, y cada vínculo debe estar en una sola página...
Los hitos importantes en el desarrollo posterior de los embebidos en libro incluyen la prueba de Mihalis Yannakakis a finales de la década de 1980 de que un grafo plano tiene un grosor de libro de cuatro como máximo, y el descubrimiento a finales de la década de 1990 de conexiones cercanas entre los embebidos en libro y la bioinformática.
Definiciones
Un libro es un tipo particular de espacio topológico, también llamado fan de semiplanos... Consiste en una sola recta , denominada lomo o contraportada del libro, junto con una colección de uno o más semiespacios, denominados páginas u hojas del libro,En inglés, los términos "spine" y "pages" es más estándar en los enfoques teóricos de grafos modernos sobre el tema. Para conocer más en detalle esta terminología, véase . teniendo cada una el lomo como límite. Los libros con un número finito de páginas pueden ser embebidos en un espacio tridimensional, por ejemplo, eligiendo para que sea el eje de un sistema tridimensional de coordenadas cartesianas y eligiendo las páginas para que sean los semiplanos cuyo ángulo diedro con respecto al plano es un múltiplo entero de .
Un dibujo de libro de un grafo finito sobre un libro es un dibujo de sobre tal que cada vértice de se representa como un punto en el lomo de , y cada vínculo de se dibuja como un curva que se encuentra dentro de una sola página de . El número de cruce del libro de la página de es el número de cruces mínimo en un dibujo del libro de páginas..
Un embebido en libro de en es un dibujo de libro que forma un grafo embebido de en . Es decir, es un dibujo de libro de en que no carece de cruces entre vínculos.
Cada grafo finito tiene un libro embebido con un número suficientemente grande de páginas. Por ejemplo, siempre es posible incrustar cada vínculo del grafo en su propia página separada.
El grosor del libro, el número de páginas o el número de pila de es el número mínimo de páginas requeridas para el embebido de en un libro.
Otro parámetro que mide la calidad del embebido 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 vínculos que puede cruzar un rayo cualquiera perpendicular al lomo dentro de una sola página. De manera equivalente (para embebidos en libro en los que cada vínculo se dibuja como una curva monótona), es el tamaño máximo de un subconjunto de vínculos dentro de una sola página de modo que los intervalos definidos en el lomo por pares de puntos finales de los vínculos que se cruzan entre sí...
Es crucial para estas definiciones que los vínculos deben permanecer dentro de una sola página del libro. Como ya observó Atneosen, si los vínculos pueden pasar de una página a otra en el lomo del libro, entonces cada grafo puede estar embebido en un libro de tres páginas. Para una embebido de libro topológico de tres páginas en el que se permiten cruces en el lomo, cada grafo puede incrustarse con un número logarítmico como máximo de cruces en el lomo por vínculo,. y algunos grafos necesitan estos cruces de vínculos en el lomo..
Grafos específicos Como se muestra en la primera figura, el grosor del libro del grafo completo es tres: como grafo no plano, su grosor del libro es mayor que dos, pero existe un libro embebido con tres páginas. Más generalmente, el grosor del libro de cada grafo completo con vértices es exactamente . Este resultado también proporciona una cota superior sobre el máximo grosor de libro posible de cualquier grafo de vértices.
El número de cruce de dos páginas del grafo completo es
haciendo valer una conjetura aún no probada de Anthony Hill sobre cuál debería ser el número de cruce sin restricciones de este grafo. Es decir, si la conjetura de Hill es correcta, entonces el dibujo de este grafo que minimiza el número de cruces es un dibujo de dos páginas..
El grosor del libro del grafo bipartito completo es como máximo . Para construir un dibujo con este grosor de libro, para cada vértice en el lado más pequeño de la bipartición, se pueden colocar los vínculos incidentes con ese vértice en su propia página. Este límite no siempre es estrecho; por ejemplo, tiene un grosor de libro de tres, no de cuatro. Sin embargo, cuando los dos lados del grafo están muy desequilibrados, con , el grosor del libro de es exactamente .Para obtener resultados adicionales sobre el grosor del libro de gráficos bipartitos completos, consúltese ; .
Para el grafo de Turán (un grafo multipartito completo formado por conjuntos independientes de vértices por conjunto independiente, con una arista entre cada dos vértices de diferentes conjuntos independientes), el grosor del libro se intercala entre
y cuando es impar, el límite superior se puede mejorar hasta
.
El grosor de un embebido en libro de grafos binarios como el grafo de De Bruijn, los grafos de intercambio aleatorio y los ciclos conectados al cubo (cuando son lo suficientemente grandes para no ser planos), es exactamente tres.; . See also .
Propiedades
Planaridad y planaridad exterior
El grosor del libro de un grafo dado es como máximo uno si y solo si es un grafo plano exterior, caracterizado por tener un embebido plano en el que todos los vértices pertenecen a la cara exterior del embebido. Para un grafo de este tipo, colocar los vértices en el mismo orden en el lomo en el que aparecen en la cara exterior proporciona un embebido de libro de una página del grafo dado (un punto de articulación del grafo aparecerá necesariamente más de una vez en el orden cíclico de los vértices alrededor de la cara exterior, pero solo una de esas copias debe incluirse en el embebido en el libro). Por el contrario, el embebido en un libro de una página es automáticamente un plano exterior, porque si un grafo está embebido en una sola página, y otro semi plano se adjunta al lomo para extender su página a un plano completo, entonces la cara exterior del embebido incluye todo el medio plano agregado, y todos los vértices se encuentran en esta cara exterior.
Cada embebido de un libro de dos páginas es un caso especial de embebido plano, porque la unión de dos páginas de un libro es un espacio topológicamente equivalente a todo el plano. Por lo tanto, cada grafo con grosor de libro dos es automáticamente un grafo plano. Más precisamente, el grosor del libro de un grafo es como máximo dos si y solo si es un subgrafo de un grafo plano que tiene un camino hamiltoniano.. Si a un grafo se le da un embebido de dos páginas, se puede aumentar a un grafo hamiltoniano plano agregando (en cualquier página) vínculos adicionales entre dos vértices consecutivos en el lomo que aún no son adyacentes, y entre el primero y el último vértices del lomo. El grafo de Goldner-Harary proporciona un ejemplo de un grafo plano que no tiene un grosor de libro dos: es un grafo plano, por lo que no es posible agregarle ningún vínculo mientras se conserva la planaridad, y no tiene un ciclo hamiltoniano. Debido a esta caracterización por ciclos hamiltonianos, los grafos que tienen embebidos en libro de dos páginas también se conocen como grafos subhamiltonianos..
Todos los grafos planos cuyo grado máximo es a lo sumo cuatro tienen un grosor de libro como máximo de dos.. Los 3-árboles planos tienen un grosor de libro de tres como máximo.. De manera más general, todos los grafos planos tienen un grosor de libro de cuatro. Mihalis Yannakakis afirmó en 1986. que existen algunos grafos planos que tienen un grosor de libro exactamente cuatro. Sin embargo, no se conoció una prueba detallada de esta afirmación hasta 2020, cuando fue presentada en un artículo de revista posterior, por Bekos et al.. que presentaron grafos planos con ancho de árbol 4 que requieren cuatro páginas en cualquier libro embebido.
Comportamiento bajo subdivisiones