Embebido en llibre

Embebido en llibre

Archiu:3page caps block 0 .svg

Un llibre de tres pàgines embebido 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 embebido en llibre és una generalisació del embebido pla d'un grafo a embebidos 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 embebido 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 embebidos 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 embebido 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 embebidos 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 embebido en llibre representen components d'un circuit i els cables representen les conexions entre ells. Els embebidos 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 embebidos 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 embebido en llibre d'este grafo per a dissenyar un cronograma que permeta que tot el tràfic es moga a través 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 del àcit ribonucleico, els embebidos en llibre d'una sola pàgina representen formes clàssiques de l'estructura secundària d'un àcit nucleico, i els embebidos en llibre de dos pàgines representen pseudonudos. Atres aplicacions de embebidos 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 embebidos de grafos en llibres. Els embebidos que va estudiar usaven la mateixa definició que els embebidos 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 embebido 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 embebidos 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 embebidos en llibre i la bioinformática.

Definicions

Archiu:Caps block 7 ,3 2-page 1-crossing.svg

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 embebido 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 finito de pàgines poden ser embebidos en un espai tridimensional, per eixemple, elegint ℓ per a que siga l'eix z d'un sistema tridimensional de coordenades cartesianas 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 finito 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 embebido en llibre de G en B és un dibuix de llibre que forma un grafo embebido 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 finito té un llibre embebido 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 embebido de  G en un llibre.

Un atre paràmetro que medix la calitat del embebido 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 embebidos 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 embebido en un llibre de tres pàgines. Per a una embebido 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.