Embegut en llibre

Embebido en llibre

Un llibre de tres pàgines incrustat del grafo complet K₅. Degut a que no és un grafo pla, no és possible embeber este grafo sense creus en menys pàgines, per lo que la gruixa del llibre és tres

En teoria de grafos, un incrustat en llibre és una generalisació de l'incrustat pla d'un grafo a incrustats en un llibre, una colecció de semiespacios, tots en la mateixa recta com a llímit. Per lo general, es requerix que els vèrtiços del grafo es troben en esta llínea llímit, cridada "columna vertebral", i es requerix que els vínculs permaneixquen dins d'un sol semiplano. La gruixa del llibre d'un grafo és el número més chicotet possible de semiplanos per a qualsevol incrustat en llibre del grafo. La gruixa del llibre també es denomina número de pàgines, número de pila o gruixa exterior fixa. Els incrustats en llibre també s'han utilisat per a definir varis atres invariantes de grafo, inclós l'ample de pàgina i el número de creus del llibre.

Cada grafo en n vèrtiços té una gruixa de llibre com a màxim de $\lceil n/2\rceil$, i esta fòrmula proporciona la gruixa del llibre exacte per a un grafo complet. Els grafos en gruixa de llibre un són els grafos plans exteriors. Els grafos en gruixa de llibre com a màxim dos es denominen grafos subhamiltonianos, que sempre són plans; de manera més general, cada grafo pla té una gruixa de llibre de quatre com a màxim. Tots els famílies de grafos tancats menors, i en particular els grafos en ample d'arbre acotat o genus acotat, també tenen gruixa de llibre acotat. Determinar la gruixa exacta del llibre d'un grafo donat, en o sense conéixer un orde de vèrtiços fix en el llom del llibre, és un problema de complexitat NP-hard. Provar l'existència d'un llibre de tres pàgines incrustat d'un grafo, donat un orde fix dels vèrtiços en el llom del llibre, té una complexitat computacional desconeguda: no se sap que siga resoluble en temps polinomial ni que siga de dificultat NP.

Una de les motivacions originals per a estudiar incrustats en llibres va involucrar aplicacions en el disseny d'integració a molt gran escala, procés en el que els vèrtiços d'un incrustat en llibre representen components d'un circuit i els cables representen les conexions entre ells. Els incrustats en llibres també té aplicacions en dibuix de grafos, a on dos dels estils de visualisació estàndar per a grafos, els diagrames d'arcs i el disseny circular, poden construir-se per mig de incrustats en llibres.

En planificació de transport, les diferents fonts i destins del tràfic peatonal i vehicular que es troben i interactuen en un semàfor es poden modelar matemàticament com els vèrtiços d'un grafo, en vínculs que conecten diferents parells d'orige i destí. Es pot usar un incrustat en llibre d'este grafo per a dissenyar un cronograma que permeta que tot el tràfic es moga per mig de l'intersecció en la menor cantitat possible de fases de semàfor. En els problemes de bioinformática que involucren l'estructura de plegat de l'àcit ribonucleico, els incrustats en llibre d'una sola pàgina representen formes clàssiques de l'estructura secundària d'un àcit nucleico, i els incrustats en llibre de dos pàgines representen pseudonudos. Atres aplicacions de incrustats en llibre inclouen l'àlgebra abstracta i la teoria de nucs.

Història

La noció de llibre, com a espai topològic, va ser definida per C. A. Persinger i Gail Atneosen en la década de 1960. Com a part d'este treball, Atneosen ya va considerar incrustats de grafos en llibres. Els incrustats que va estudiar usaven la mateixa definició que els incrustats de grafos en qualsevol atre espai topològic: els vèrtiços estan representats per punts distints, els vínculs estan representats per curves i l'única forma en que dos vínculs poden intersecarse és que es troben en un punt final comú.

A principis de la década de 1970, Paul C. Kainen i L. Taylor Ollmann varen desenrollar un tipo de incrustat més restringit que es va utilisar en la majoria de les investigacions posteriors. En la seua formulació, els vèrtiços del grafo deuen colocar-se en el llom del llibre, i cada víncul deu estar en una sola pàgina.

Les fites importants en el desenroll posterior dels incrustats en llibre inclouen la prova de Mihalis Yannakakis a finals de la década de 1980 de que un grafo pla té una gruixa de llibre de quatre com a màxim, i el descobriment a finals de la década de 1990 de conexions propenques entre els incrustats en llibre i la bioinformática.

Definicions

El grafo del problema dels tres servicis K_3,3 no es pot embeber en un llibre de 2 pàgines, pero es pot dibuixar com es mostra en un llibre de 2 pàgines en un sol creuament. Per lo tant, el seu número de creuament per a llibres de 2 pàgines és 1

Este incrustat d'1 pàgina del grafo diamant té un ample de pàgina de 3, perque el raig groc creua tres vínculs

Un llibre és un tipo particular d'espai topològic, també cridat fan de semiplanos. Consistix en una sola recta ℓ, denominada llom o contraportada del llibre, junt en una colecció d'un o més semiespacios, denominats pàgines o fulls del llibre, tenint cada una el llom com a llímit. Els llibres en un número finit de pàgines poden ser incrustats en un espai tridimensional, per eixemple, elegint ℓ per a que siga l'eix z d'un sistema tridimensional de coordenades cartesianes i elegint les pàgines per a que siguen els semiplanos k que el seu àngul diedro sobre el pla xz és un múltiple sancer de 2Π/k.

Un dibuix de llibre d'un grafo finit G sobre un llibre B és un dibuix de G sobre B tal que cada vèrtiç de G es representa com un punt en el llom de B, i cada víncul de G es dibuixa com un curva que es troba dins d'una sola pàgina de B. El número de creuament del llibre de la pàgina k de G és el número de creus mínim en un dibuix del llibre de k pàgines.

Un incrustat en llibre de G en B és un dibuix de llibre que forma un grafo incrustat de G en B. És dir, és un dibuix de llibre de G en B que no carix de creus entre vínculs.

Cada grafo finit té un llibre incrustat en un número suficientment gran de pàgines. Per eixemple, sempre és possible incrustar cada víncul del grafo en la seua pròpia pàgina separada.

La gruixa del llibre, el número de pàgines o el número de pila de G és el número mínim de pàgines requerides per al incrustat de  G en un llibre.

Un atre paràmetro que medix la calitat de l'incrustat d'un llibre, més allà del seu número de pàgines, és el seu ample de pàgina. Est és el número màxim de vínculs que pot creuar un raig qualsevol perpendicular al llom dins d'una sola pàgina. De manera equivalent (per a incrustats en llibre en els que cada víncul es dibuixa com una curva monòtona), és el tamany màxim d'un subconjunt de vínculs dins d'una sola pàgina de modo que els intervals definits en el llom per parells de punts finals dels vínculs que es creuen entre sí.

És crucial per a estes definicions que els vínculs deuen permanéixer dins d'una sola pàgina del llibre. Com ya va observar Atneosen, si els vínculs poden passar d'una pàgina a una atra en el llom del llibre, llavors cada grafo pot estar incrustat en un llibre de tres pàgines. Per a una incrustat de llibre topològic de tres pàgines en el que es permeten creus en el llom, cada grafo pot incrustar-se en un número logarítmic com a màxim de creus en el llom per víncul, i alguns grafos necessiten estos creus de vínculs en el llom.