Incrustaciones de grafos

En la teoría topológica de grafos , una incrustación (también escrita como imbedding ) de un grafo${\displaystyle G}$sobre una superficie${\displaystyle \Sigma }$es una representación de${\displaystyle G}$en${\displaystyle \Sigma }$en qué puntos de${\displaystyle \Sigma }$están asociados con vértices y arcos simples ( imágenes homeomórficas de${\displaystyle [0,1]}$) están asociados con aristas de tal manera que:

• los extremos del arco asociados a una arista${\displaystyle e}$son los puntos asociados con los vértices finales de${\displaystyle e,}$
• Ningún arco incluye puntos asociados a otros vértices,
• Dos arcos nunca se intersecan en un punto que sea interior a cualquiera de los arcos.

Aquí una superficie es una conexión${\displaystyle 2}$- colector .

De manera informal, una incrustación de un grafo en una superficie es un dibujo del grafo sobre la superficie de tal forma que sus aristas solo se intersecan en sus extremos. Es bien sabido que cualquier grafo finito puede incrustarse en un espacio euclidiano tridimensional.${\displaystyle \mathbb {R} ^{3}}$. ^{[ 1 ]} Un grafo planar es aquel que puede incrustarse en un espacio euclidiano bidimensional.${\displaystyle \mathbb {R} ^{2}.}$

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

Algunos autores definen una versión más débil de la definición de "incrustación de grafos" omitiendo la condición de no intersección para las aristas. En tales contextos, la definición más estricta se describe como "incrustación de grafos sin cruces". ^{[ 2 ]}

Este artículo se centra únicamente en la definición estricta de incrustación de grafos. La definición menos estricta se analiza en los artículos " Dibujo de grafos " y " Número de cruces ".

Si un gráfico${\displaystyle G}$está incrustado en una superficie cerrada${\displaystyle \Sigma }$, el complemento de la unión de los puntos y arcos asociados con los vértices y aristas de${\displaystyle G}$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 grafo es el entero mínimo${\displaystyle n}$de tal manera que el gráfico pueda incrustarse en una superficie de género${\displaystyle n}$. En particular, un grafo planar tiene género${\displaystyle 0}$, porque se puede dibujar en una esfera sin autocruzarse. Un grafo que se puede incrustar en un toro se llama grafo toroidal .

El género no orientable de un grafo es el entero mínimo${\displaystyle n}$de tal manera que el gráfico pueda incrustarse en una superficie no orientable de género (no orientable)${\displaystyle n}$. ^{[ 3 ]}

El género de Euler de un grafo es el entero mínimo${\displaystyle n}$de tal manera que el gráfico pueda incrustarse en una superficie orientable de género (orientable)${\displaystyle n/2}$o en una superficie no orientable del género (no orientable)${\displaystyle n}$Un grafo es orientablemente simple si su género de Euler es menor que su género no orientable.

El género máximo de un grafo es el entero máximo${\displaystyle n}$de tal manera que el gráfico pueda ser${\displaystyle 2}$-célula incrustada en una superficie orientable de género${\displaystyle n}$.

Un grafo 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 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). En ocasiones, el propio sistema de rotación se denomina "incrustación combinatoria". ^{[ 5 ] [ 6 ] [ 7 ]}

Un grafo incrustado también define órdenes cíclicas naturales de aristas que constituyen los límites de las caras de la incrustación. Sin embargo, manejar estos órdenes basados ​​en caras es menos sencillo, ya que en algunos casos algunas aristas pueden recorrerse dos veces a lo largo del límite de una cara. Por ejemplo, esto siempre ocurre en las incrustaciones de árboles, que tienen una sola cara. Para superar este inconveniente combinatorio, se puede considerar que cada arista se "divide" longitudinalmente en dos "semiaristas" o "lados". Bajo esta convención, en todos los recorridos de los límites de las caras, cada semiarista se recorre solo una vez y las dos semiaristas de la misma arista siempre se recorren en direcciones opuestas.

Otras representaciones equivalentes para incrustaciones celulares incluyen el grafo de cinta , un espacio topológico formado al pegar discos topológicos para los vértices y aristas de un grafo incrustado, y el mapa codificado en grafo , un grafo cúbico con aristas coloreadas con cuatro vértices para cada arista del grafo incrustado.

El problema de encontrar el género del grafo es NP-difícil (el problema de determinar si un${\displaystyle n}$-el grafo de vértices tiene género${\displaystyle g}$es NP-completo ). ^{[ 8 ]}

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

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

En 1999 se informó que el caso de género fijo se puede resolver en un tiempo lineal en el tamaño del grafo y doblemente exponencial en el género. ^{[ 11 ]}

Se sabe que cualquier grafo finito puede incrustarse en un espacio tridimensional. ^{[ 1 ]}

Un método para lograr esto consiste en colocar los puntos sobre cualquier línea en el espacio y dibujar las aristas como curvas, cada una ubicada en un semiplano distinto , con esa línea como límite común para todos los semiplanos. Una incrustación de este tipo, en la que las aristas se dibujan sobre semiplanos, se denomina incrustación en libro del grafo. Esta metáfora surge de imaginar que cada uno de los planos donde se dibuja una arista es como una página de un libro. Se observó que, de hecho, se pueden dibujar varias aristas en la misma "página"; el grosor del libro del grafo es el número mínimo de semiplanos necesarios para tal dibujo.

Alternativamente, cualquier grafo finito puede dibujarse con aristas rectas en tres dimensiones sin cruces colocando sus vértices en una posición general de manera que no haya cuatro coplanares. Por ejemplo, esto puede lograrse colocando el i -ésimo vértice en el punto ( i , i2 , i3 ⁾ de la curva de ^momento .

Una incrustación de un grafo en un espacio tridimensional en la que ningún par de ciclos están vinculados topológicamente se denomina incrustación sin enlaces . Un grafo tiene una incrustación sin enlaces si y solo si no tiene como menor ninguno de los siete grafos de la familia de Petersen .

• 
  El gráfico de Petersen y el mapa asociado están incrustados en el plano proyectivo. Se identifican puntos opuestos en el círculo, lo que da como resultado una superficie cerrada de género 1 no orientable.
• 
  El grafo de Pappus y el mapa asociado incrustados en el toro.
• 
  El grafo de Klein de grado 7 y el mapa asociado incrustados en una superficie orientable de género 3.

• Incrustación , para otros tipos de incrustaciones
• Grosor del libro
• Grosor del gráfico
• Lista de aristas doblemente conectadas , una estructura de datos para representar una incrustación de grafo en el plano
• Mapa regular (teoría de grafos)
• El teorema de Fáry , que establece que siempre es posible una incrustación planar en línea recta de un grafo planar.
• Triangulación (geometría)