Incrustación de gráficos - Graph embedding

El gráfico de Heawood y el mapa asociado incrustados en el toro.

En la teoría de grafos topológica , una incrustación (también escrito imbedding ) de un gráfico en una superficie es una representación de sobre en el que puntos de están asociados con vértices y arcos simples ( homeomórficos imágenes de ) están asociados con los bordes de una manera tal que: ${\ Displaystyle G}$ ${\ Displaystyle \ Sigma}$${\ Displaystyle G}$${\ Displaystyle \ Sigma}$${\ Displaystyle \ Sigma}$${\ Displaystyle [0,1]}$

• los puntos finales del arco asociados con una arista son los puntos asociados con los vértices finales de${\ Displaystyle e}$${\ Displaystyle e,}$
• ningún arco incluye puntos asociados con otros vértices,
• dos arcos nunca se cruzan en un punto que es interior a cualquiera de los arcos.

Aquí una superficie es un compacto , conectado - colector . ${\ Displaystyle 2}$

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 pueden cruzarse solo en sus puntos finales. Es bien sabido que cualquier gráfico finito puede incrustarse en un espacio euclidiano tridimensional . Un gráfico plano es aquel que se puede incrustar en un espacio euclidiano bidimensional.${\ Displaystyle \ mathbb {R} ^ {3}}$${\ Displaystyle \ mathbb {R} ^ {2}.}$

A menudo, una incrustación se considera una clase de equivalencia (bajo homeomorfismos de ) de representaciones del tipo que se acaba de describir. ${\ Displaystyle \ Sigma}$

Algunos autores definen una versión más débil de la definición de "incrustación de gráficos" omitiendo la condición de no intersección para los bordes. En tales contextos, la definición más estricta se describe como "incrustación de gráficos no cruzados".

Este artículo se ocupa ú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áfico " y " número de cruce ".

Terminología

Si un gráfico está incrustado en una superficie cerrada , el complemento de la unión de los puntos y arcos asociados con los vértices y aristas de es una familia de regiones (o caras ). Una incrustación de 2 celdas , una incrustación celular o un mapa es una incrustación en la que cada rostro es homeomórfico a un disco abierto. Una incrustación cerrada de 2 celdas es una incrustación en la que el cierre de cada cara es homeomórfico a un disco cerrado. ${\ Displaystyle G}$${\ Displaystyle \ Sigma}$${\ Displaystyle G}$

El género de un gráfico es el número entero mínimo tal que el gráfico se puede incrustar en una superficie de género . En particular, un gráfico plano tiene género , porque se puede dibujar en una esfera sin autocruzamiento. El género no orientable de un gráfico es el número entero mínimo tal que el gráfico se puede incrustar en una superficie no orientable de género (no orientable) . ${\ Displaystyle n}$ ${\ Displaystyle n}$${\ displaystyle 0}$${\ Displaystyle n}$${\ Displaystyle n}$

El género Euler de un gráfico es el número entero mínimo tal que el gráfico se puede incrustar en una superficie orientable de género (orientable) o en una superficie no orientable de género (no orientable) . Un gráfico es orientablemente simple si su género Euler es más pequeño que su género no orientable. ${\ Displaystyle n}$${\ Displaystyle n / 2}$${\ Displaystyle n}$

El género máximo de un gráfico es el número entero máximo de modo que el gráfico se puede incrustar en una celda orientable de la superficie del género . ${\ Displaystyle n}$${\ Displaystyle 2}$ ${\ Displaystyle n}$

Incrustación combinatoria

Un gráfico incrustado define de forma única órdenes cíclicas de aristas incidentes al mismo vértice. El conjunto de todos estos órdenes cíclicos se denomina 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 "incorporación combinatoria".

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, el manejo de estos pedidos basados ​​en caras es menos sencillo, ya que en algunos casos algunos bordes se pueden atravesar dos veces a lo largo de un límite de cara. Por ejemplo, este es siempre el caso de las incrustaciones de árboles, que tienen una sola cara. Para superar esta molestia combinatoria, se puede considerar que cada borde se "divide" longitudinalmente en dos "medios bordes" o "lados". Según esta convención, en todos los recorridos de límites de caras, cada medio borde se atraviesa solo una vez y los dos medios bordes del mismo borde 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 bordes de un gráfico incrustado, y el mapa codificado por gráficos , un gráfico cúbico de color de borde con cuatro vértices para cada borde el gráfico incrustado.

Complejidad computacional

El problema de encontrar el género del gráfico es NP-difícil (el problema de determinar si un gráfico -vertex tiene género es NP-completo ). ${\ Displaystyle n}$${\ Displaystyle g}$

Al mismo tiempo, el problema del género gráfico es manejable con parámetros fijos , es decir, se conocen algoritmos de tiempo polinomial para verificar si un gráfico puede incrustarse en una superficie de un género fijo dado, así como para encontrar la incrustación.

El primer avance en este sentido ocurrió en 1979, cuando los algoritmos de complejidad temporal O ( n ^{O ( g )} ) se presentaron de forma independiente al Simposio Anual de ACM sobre Teoría de la Computación : uno de I. Filotti y GL Miller y otro de John Reif. . Sus enfoques fueron bastante diferentes, pero por sugerencia del comité del programa, presentaron un documento conjunto. Sin embargo, Wendy Myrvold y William Kocay demostraron en 2011 que el algoritmo dado por Filotti, Miller y Reif era incorrecto.

En 1999 se informó que el caso de género fijo puede resolverse en el tiempo lineal en el tamaño del gráfico y doblemente exponencial en el género.

Incrustaciones de gráficos en espacios de dimensiones superiores

Se sabe que cualquier gráfico finito se puede incrustar en un espacio tridimensional.

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 , y todos los semiplanos tienen esa línea como límite común. Una incrustación como esta en la que los bordes se dibujan en medios planos se denomina incrustación de libro del gráfico. Esta metáfora surge de imaginar que cada uno de los planos donde se dibuja un borde es como la página de un libro. Se observó que, de hecho, se pueden dibujar varios bordes en la misma "página"; el grosor del libro del gráfico es el número mínimo de medios planos necesarios para tal dibujo.

Alternativamente, cualquier gráfico finito se puede dibujar con bordes en línea recta en tres dimensiones sin cruces colocando sus vértices en posición general de modo que no haya cuatro coplanares. Por ejemplo, esto se puede lograr colocando el i- ésimo vértice en el punto ( i , i ² , i ³ ) de la curva de momentos .

Una incrustación de un gráfico en un espacio tridimensional en el que no hay dos ciclos vinculados topológicamente se denomina incrustación sin enlace . Un gráfico tiene una incrustación sin enlaces si y solo si no tiene uno de los siete gráficos de la familia Petersen como menor .

Galería

• 

  El gráfico de Petersen y el mapa asociado incrustados en el plano proyectivo. Los puntos opuestos del círculo se identifican dando como resultado una superficie cerrada del género 1 no orientable.

• 

  El gráfico de Pappus y el mapa asociado incrustados en el toro.

• 

  El gráfico de Klein de grado 7 y el mapa asociado incrustados en una superficie orientable del género 3.

Ver también

• Incrustaciones , para otros tipos de incrustaciones
• Espesor del libro
• Espesor del gráfico
• Lista de bordes doblemente conectados , una estructura de datos para representar un gráfico incrustado en el plano
• Mapa regular (teoría de grafos)
• El teorema de Fáry , que dice que siempre es posible una incrustación plana en línea recta de un gráfico plano.
• Triangulación (geometría)

Referencias