Embebido en libro
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.
, y esta fórmula proporciona el grosor del libro exacto para un grafo completo.
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.
[1][8] 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,[9] teniendo cada una el lomo como límite.
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.
[12][13][14] 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.
Más generalmente, el grosor del libro de cada grafo completo con n ≥ 4 vértices es exactamente
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.
[21] El grosor del libro de un grafo G dado es como máximo uno si y solo si G es un grafo plano exterior, caracterizado por tener un embebido plano en el que todos los vértices pertenecen a la cara exterior del embebido.
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.
Más precisamente, el grosor del libro de un grafo G es como máximo dos si y solo si G es un subgrafo de un grafo plano que tiene un camino hamiltoniano.
[10] Si a un grafo se le da un embebido de dos páginas, se puede aumentar a un grafo hamiltoniano plano agregando (en cualquier página) vínculos adicionales entre dos vértices consecutivos en el lomo que aún no son adyacentes, y entre el primero y el último vértices del lomo.
El grafo de Goldner-Harary proporciona un ejemplo de un grafo plano que no tiene un grosor de libro dos: es un grafo plano, por lo que no es posible agregarle ningún vínculo mientras se conserva la planaridad, y no tiene un ciclo hamiltoniano.
Específicamente, se propuso que existe una función f tal que, para cada grafo G y para el grafo H formado reemplazando cada vínculo en G por un camino de dos vínculos, que si el grosor del libro de H es t entonces el grosor del libro de G es como máximo f(t).
Aquí, n se refiere al número de vértices en el grafo.
Esto se puede formalizar considerando una secuencia arbitraria de operaciones empujar y eliminar elementos en una pila, y formando un grafo en el que las operaciones de la pila corresponden a los vértices del grafo, colocados en orden secuencial en el lomo de un libro embebido.
Luego, en este grafo, cada dos vínculos se cruzarán o cubrirán intervalos inconexos en el lomo.
Por analogía, los investigadores han definido un embebido en cola de un grafo como una embebido en un libro topológico, de modo que cada vértice se encuentra en el lomo, cada vínculo se encuentra en una sola página y cada dos vínculos en la misma página se cruzan o cubren intervalos disjuntos en el lomo.
Esto se deriva del hecho de que encontrar ciclos hamiltonianos en grafos planos máximos es una tarea NP-completa.
Por lo tanto, también es una tarea NP-completa probar si el grosor del libro de un grafo plano máximo dado es dos.
[42] Si se desconoce el orden del lomo pero se proporciona una partición de los vínculos en dos páginas, entonces es posible encontrar una embebido de 2 páginas (si existe) en tiempo lineal mediante un algoritmo basado en un árbol SPQR.
[48] Bekos, Kaufmann y Zielke (2015) describió un sistema para encontrar embebidos en libro óptimos transformando el problema en una instancia de satisfacibilidad booleana y aplicando un solucionador SAT al problema resultante.
En el sistema DIOGENES desarrollado por estos autores, la unidad central de procesamiento de un sistema multiprocesador se organizan en una secuencia lógica correspondiente al lomo de un libro (aunque esta secuencia no necesariamente se coloca en una línea en el diseño físico del sistema).
observaron, una permutación dada puede ser ordenada por este sistema si y solo si un cierto grafo, derivado de la permutación, tiene un libro embebido con los vértices en un cierto orden fijo en el lomo y con un número de páginas que es como máximo igual al número de pilas.
[55] Un diagrama de arcos[52] o embebido lineal[42] coloca los vértices de un grafo en una recta y dibuja los vínculos del grafo como semicírculos por encima o por debajo de esta línea, y a veces también se permite dibujar vínculos en segmentos sobre la propia línea recta.
[58] Para cada grafo plano, siempre es posible encontrar un embebido en el que cada vínculo cruce la recta donde se sitúan los vértices como máximo una vez.
[65] Pavan, Tewari y Vinodchandran (2012) utilizó el embebido de libros para estudiar el teoría de la complejidad computacional del problema reachability en grafo dirigido.
Por lo tanto, los embebidos en libro parecen estar íntimamente conectadas con la distinción entre estas dos clases de complejidad.
