Incorporación de gráficos

Incrustar un gráfico en un espacio topológico, a menudo euclidiano

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

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

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

Aquí una superficie es una variedad conexa . ${\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 intersecarse solo en sus puntos finales. Es bien sabido que cualquier gráfico finito puede incrustarse en el espacio euclidiano tridimensional . ^[1] Un gráfico plano es uno que puede incrustarse en el espacio euclidiano bidimensional . ${\displaystyle \mathbb {R} ^{3}}$ ${\displaystyle \mathbb {R} ^{2}.}$

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

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 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 ".

Terminología

Si un grafo 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 ). ^[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 homeomorfa a un disco cerrado. ${\displaystyle G}$ ${\displaystyle \Sigma }$ ${\displaystyle G}$

El género de un grafo es el entero mínimo tal que el grafo puede ser embebido en una superficie de género . En particular, un grafo plano tiene género , porque puede ser dibujado en una esfera sin autocruzarse. Un grafo que puede ser embebido en un toro se llama grafo toroidal . ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 0}$

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

El género de Euler de un grafo es el entero mínimo tal que el grafo puede ser embebido 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 de Euler es menor que su género no orientable. ${\displaystyle n}$ ${\displaystyle n/2}$ ${\displaystyle n}$

El género máximo de un gráfico es el entero máximo tal que el gráfico puede ser incrustado en una superficie orientable de género . ${\displaystyle n}$ ${\displaystyle 2}$ ${\displaystyle n}$

Incorporación combinatoria

Un grafo embebido define de forma única órdenes cíclicos 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 propio sistema de rotación se denomina "incrustación combinatoria". ^{[5] [6] [7]}

Un grafo 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 órdenes basados ​​en caras es menos sencillo, ya que en algunos casos algunas aristas pueden atravesarse 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 arista se "divida" longitudinalmente en dos "medias aristas" o "lados". Bajo esta convención, en todos los recorridos de límites de caras, cada media arista se atraviesa solo una vez y las dos medias aristas de la misma arista siempre se recorren en direcciones opuestas.

Otras representaciones equivalentes para incrustaciones celulares incluyen el gráfico de cinta , un espacio topológico formado al pegar juntos discos topológicos para los vértices y los bordes de un gráfico incrustado, y el mapa codificado por gráficos , un gráfico cúbico con bordes coloreados con cuatro vértices para cada borde del gráfico incrustado.

Complejidad computacional

El problema de encontrar el género del grafo es NP-difícil (el problema de determinar si un grafo de -vértice tiene género es NP-completo ). ^[8] ${\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 se produjo en 1979, cuando se presentaron de forma independiente algoritmos de complejidad temporal O ( n ^{O ( g ) ) en el} 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 por sugerencia del comité del programa presentaron un artículo 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 de forma lineal en el tamaño del gráfico y doblemente exponencial en el género. ^[11]

Incrustaciones de gráficos en espacios de dimensiones superiores

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 las aristas como curvas, cada una de las cuales se encuentra en un semiplano distinto , con todos los semiplanos teniendo esa línea como su límite común. Una incrustación como esta en la que las aristas se dibujan en semiplanos se llama incrustación de libro del gráfico. Esta metáfora proviene 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 gráfico 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 posición general de modo 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 momentos} .

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

Galería

• 
  El gráfico de Petersen y el mapa asociado están incrustados en el plano proyectivo. Se identifican los puntos opuestos en el círculo, lo que da como resultado una superficie cerrada de género no orientable 1.
• 
  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 están incrustados en una superficie orientable de género 3.

Véase también

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

Referencias

1. Cohen, Robert F.; Eades, Peter ; Lin, Tao; Ruskey, Frank (1995), "Dibujo de grafos tridimensionales", en Tamassia, Roberto ; Tollis, Ioannis G. (eds.), Graph Drawing: DIMACS International Workshop, GD '94 Princeton, Nueva Jersey, EE. UU., 10-12 de octubre de 1994, Actas , Lecture Notes in Computer Science , vol. 894, Springer, págs. 1-11, doi : 10.1007/3-540-58950-3_351 , ISBN 978-3-540-58950-1.
2. Katoh, Naoki; Tanigawa, Shin-ichi (2007), "Enumeración de árboles de expansión geométricos no cruzados restringidos", Computing and Combinatorics, 13.ª conferencia internacional anual, COCOON 2007, Banff, Canadá, 16-19 de julio de 2007, Actas , Lecture Notes in Computer Science , vol. 4598, Springer-Verlag, págs. 243–253, CiteSeerX 10.1.1.483.874 , doi :10.1007/978-3-540-73545-8_25, ISBN  978-3-540-73544-1.
3. Gross, Jonathan; Tucker, Thomas W. (2001), Teoría de grafos topológicos , Dover Publications, ISBN 978-0-486-41741-7.
4. Lando, Sergei K.; Zvonkin, Alexander K. (2004), Gráficos sobre superficies y sus aplicaciones , Springer-Verlag, ISBN 978-3-540-00203-1.
5. Mutzel, Petra ; Weiskircher, René (2000), "Computing Optimal Embeddings for Planar Graphs", Computing and Combinatorics, 6th Annual International Conference, COCOON 2000, Sydney, Australia, 26-28 de julio de 2000, Actas , Lecture Notes in Computer Science, vol. 1858, Springer-Verlag, págs. 95-104, doi :10.1007/3-540-44968-X_10, ISBN 978-3-540-67787-1.
6. Didjev, Hristo N. (1995), "Sobre el dibujo de un gráfico de forma convexa en el plano", Graph Drawing, DIMACS International Workshop, GD '94, Princeton, Nueva Jersey, EE. UU., 10-12 de octubre de 1994, Proceedings , Lecture Notes in Computer Science, vol. 894, Springer-Verlag, págs. 76-83, doi : 10.1007/3-540-58950-3_358 , ISBN 978-3-540-58950-1.
7. Duncan, Christian; Goodrich, Michael T .; Kobourov, Stephen (2010), "Planar Drawings of Higher-Genus Graphs", Graph Drawing, 17th International Symposium, GD 2009, Chicago, IL, EE. UU., 22-25 de septiembre de 2009, Documentos revisados , Lecture Notes in Computer Science, vol. 5849, Springer-Verlag, págs. 45–56, arXiv : 0908.1608 , doi :10.1007/978-3-642-11805-0_7, ISBN 978-3-642-11804-3.
8. Thomassen, Carsten (1989), "El problema del género gráfico es NP-completo", Journal of Algorithms , 10 (4): 568–576, doi :10.1016/0196-6774(89)90006-0
9. Filotti, IS; Miller, Gary L .; Reif, John (1979), "Sobre la determinación del género de un grafo en pasos O(v O(g)) (Informe preliminar)", Proc. 11th Annu. ACM Symposium on Theory of Computing , págs. 27–37, doi : 10.1145/800135.804395.
10. Myrvold, Wendy ; Kocay, William (1 de marzo de 2011). "Errores en algoritmos de incrustación de grafos". Revista de Ciencias de la Computación y de Sistemas . 2 (77): 430–438. doi :10.1016/j.jcss.2010.06.002.
11. Mohar, Bojan (1999), "Un algoritmo de tiempo lineal para incrustar gráficos en una superficie arbitraria", SIAM Journal on Discrete Mathematics , 12 (1): 6–26, CiteSeerX 10.1.1.97.9588 , doi :10.1137/S089548019529248X