![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/d/d4/3page_K5.svg/langes-640px-3page_K5.svg.png&w=640&q=50)
Embebido en libro
disposición de un grafo en varios semiplanos con una recta común en la que se sitúan los nodos / De Wikipedia, la enciclopedia encyclopedia
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.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d4/3page_K5.svg/320px-3page_K5.svg.png)
Cada grafo con n 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.