En teoría de grafos topológicos , una incrustación (también deletreada incrustación ) de un gráfico en una superficie es una representación de en la cual los puntos de están asociados con vértices y los arcos simples ( imágenes homeomórficas de ) están asociados con bordes de tal manera que:
Aquí una superficie es una variedad conexa .
De manera informal, una incrustación de un gráfico en una superficie es un dibujo del gráfico en la superficie de tal manera que sus bordes puedan cruzarse solo en sus puntos finales. Es bien sabido que cualquier gráfico finito puede incrustarse en un espacio euclidiano tridimensional . [1] Un gráfico plano es aquel que se puede incrustar en un espacio euclidiano bidimensional.
A menudo, una incrustación se considera una clase de equivalencia (bajo homeomorfismos de ) de representaciones del tipo que acabamos de describir.
Algunos autores definen una versión más débil de la definición de "incrustación de gráficos" al omitir la condición de no intersección de los bordes. En tales contextos, la definición más estricta se describe como "incrustación de gráficos sin cruces". [2]
Este artículo trata únicamente de la definición estricta de incrustación de gráficos. La definición más débil se analiza en los artículos " dibujo de gráficos " y " número de cruce ".
Si un gráfico está incrustado en una superficie cerrada , el complemento de la unión de los puntos y arcos asociados a los vértices y aristas de es una familia de regiones (o caras ). [3] Una incrustación de 2 celdas , incrustación celular o mapa es una incrustación en la que cada cara es homeomorfa a un disco abierto. [4] Una incrustación cerrada de 2 celdas es una incrustación en la que el cierre de cada cara es homeomorfo a un disco cerrado.
El género de un gráfico es el número entero mínimo tal que el gráfico puede incrustarse en una superficie de género . En particular, un gráfico plano tiene género porque se puede dibujar en una esfera sin autocruzarse. Un gráfico que se puede incrustar en un toroide se llama gráfico toroidal .
El género no orientable de un gráfico es el número entero mínimo tal que el gráfico puede incrustarse en una superficie no orientable de género (no orientable) . [3]
El género Euler de un gráfico es el número entero mínimo tal que el gráfico puede estar incrustado en una superficie orientable de género (orientable) o en una superficie no orientable de género (no orientable) . Un grafo es orientablemente simple si su género Euler es más pequeño que su género no orientable.
El género máximo de un gráfico es el número entero máximo tal que el gráfico puede estar incrustado en una superficie orientable de género .
Un gráfico incrustado define de forma única los órdenes cíclicos de aristas incidentes en el mismo vértice. Al conjunto de todos estos órdenes cíclicos se le llama sistema de rotación . Las incrustaciones con el mismo sistema de rotación se consideran equivalentes y la clase de equivalencia correspondiente de incrustaciones se denomina incrustación combinatoria (a diferencia del término incrustación topológica , que se refiere a la definición anterior en términos de puntos y curvas). A veces, el sistema de rotación en sí se denomina "incrustación combinatoria". [5] [6] [7]
Un gráfico incrustado también define órdenes cíclicos naturales de aristas que constituyen los límites de las caras de la incrustación. Sin embargo, manejar estas órdenes basadas en caras es menos sencillo, ya que en algunos casos algunos bordes pueden atravesarse dos veces a lo largo de un límite de cara. Por ejemplo, este es siempre el caso de los empotramientos de árboles, que tienen una sola cara. Para superar esta molestia combinatoria, se puede considerar que cada borde está "dividido" longitudinalmente en dos "medios bordes" o "lados". Según esta convención, en todos los recorridos de límites de caras, cada media arista se atraviesa sólo una vez y las dos medias aristas de la misma arista siempre se atraviesan en direcciones opuestas.
Otras representaciones equivalentes para incrustaciones celulares incluyen el gráfico de cinta , un espacio topológico formado al pegar discos topológicos para los vértices y aristas de un gráfico incrustado, y el mapa codificado por gráfico , un gráfico cúbico de color de borde con cuatro vértices para cada borde de el gráfico incrustado.
El problema de encontrar el género del gráfico es NP-difícil (el problema de determinar si un gráfico de vértice tiene género es NP-completo ). [8]
Al mismo tiempo, el problema del género de gráficos es manejable con parámetros fijos , es decir, se sabe que los algoritmos de tiempo polinomial verifican si un gráfico se puede incrustar en una superficie de un género fijo determinado, así como para encontrar la incrustación.
El primer avance a este respecto se produjo en 1979, cuando se presentaron de forma independiente algoritmos de complejidad temporal O ( n O ( g ) ) al Simposio Anual de Teoría de la Computación de la ACM : uno de I. Filotti y GL Miller y otro de John Reif. . Sus enfoques eran bastante diferentes, pero por sugerencia del comité del programa presentaron un documento conjunto. [9] Sin embargo, Wendy Myrvold y William Kocay demostraron en 2011 que el algoritmo dado por Filotti, Miller y Reif era incorrecto. [10]
En 1999 se informó que el caso de género fijo se puede resolver en el tiempo lineal en el tamaño del gráfico y doblemente exponencial en el género. [11]
Se sabe que cualquier gráfico finito puede integrarse en un espacio tridimensional. [1]
Un método para hacer esto es colocar los puntos en cualquier línea en el espacio y dibujar los bordes como curvas, cada una de las cuales se encuentra en un semiplano distinto , teniendo todos los semiplanos esa línea como límite común. Una incrustación como esta en la que los bordes se dibujan en semiplanos se llama incrustación en libro del gráfico. Esta metáfora surge de imaginar que cada uno de los planos donde se dibuja un borde es como una página de un libro. Se observó que, de hecho, se pueden dibujar varios bordes en una misma "página"; El espesor del libro del gráfico es el número mínimo de semiplanos necesarios para dicho dibujo.
Alternativamente, cualquier gráfico finito se puede dibujar con aristas rectas en tres dimensiones sin cruces colocando sus vértices en posición general de modo que ninguno de los cuatro sea coplanar. Por ejemplo, esto se puede lograr colocando el i- ésimo vértice en el punto ( i , i 2 , i 3 ) de la curva de momento .
Una incrustación de un gráfico en un espacio tridimensional en el que dos de los ciclos no están vinculados topológicamente se denomina incrustación sin vínculos . Un grafo tiene una incrustación sin vínculos si y sólo si no tiene uno de los siete grafos de la familia Petersen como menor .