Incrustació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 toroide.

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: ${\displaystyle G}$ ${\displaystyle \Sigma }$ ${\displaystyle G}$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma }$ ${\displaystyle [0,1]}$

• los puntos finales del arco asociado con un borde 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 interior a cualquiera de los arcos.

Aquí una superficie es una variedad compacta ^{[ cita} requerida ^] conectada . ${\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 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. ${\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 acabamos de describir. ${\displaystyle \Sigma }$

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

Terminología

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. ${\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 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 . ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 0}$

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] ${\displaystyle n}$ ${\displaystyle n}$

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. ${\displaystyle n}$ ${\displaystyle n/2}$ ${\displaystyle n}$

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 . ${\displaystyle n}$ ${\displaystyle 2}$ ${\displaystyle n}$

Incrustación combinatoria

Un gráfico incrustado define de forma única ó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.

Complejidad computacional

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] ${\displaystyle n}$ ${\displaystyle g}$

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 ACM sobre Teoría de la Computación : 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]

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 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 en realidad 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 ² , i ³ ) 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 .

Galería

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

Ver también

• Incrustaciones , para otro tipo 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)
• 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

1. Cohen, Robert F.; Eades, Pedro ; Lin, Tao; Ruskey, Frank (1995), "Dibujo de gráficos tridimensionales", en Tamassia, Roberto ; Tollis, Ioannis G. (eds.), Dibujo gráfico: Taller internacional DIMACS, GD '94 Princeton, Nueva Jersey, EE. UU., 10 al 12 de octubre de 1994, Actas , Lecture Notes in Computer Science , vol. 894, Springer, págs. 1 a 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", Computación y combinatoria, 13ª Conferencia Internacional Anual, COCOON 2007, Banff, Canadá, 16 al 19 de julio de 2007, Actas , Apuntes de conferencias sobre informática , 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. bruto, Jonathan; Tucker, Thomas W. (2001), Teoría de grafos topológicos , Publicaciones de Dover, 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 al 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 dibujar un gráfico convexo en el plano", Dibujo de gráficos, Taller internacional DIMACS, GD '94, Princeton, Nueva Jersey, EE. UU., 10 al 12 de octubre de 1994, Actas , Notas de conferencias en Ciencias de la Computación, vol. 894, Springer-Verlag, págs. 76–83, doi : 10.1007/3-540-58950-3_358 , ISBN 978-3-540-58950-1.
7. Duncan, cristiano; Goodrich, Michael T .; Kobourov, Stephen (2010), "Planar Drawings of Higher-Genus Graphs", Graph Drawing, 17º Simposio Internacional, GD 2009, Chicago, IL, EE. UU., 22 al 25 de septiembre de 2009, artículos revisados , notas de conferencias sobre informática, 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 de gráficos es NP-completo", Journal of Algorithms , 10 (4): 568–576, doi :10.1016/0196-6774(89)90006-0
9. Filotti, ES; Miller, Gary L .; Reif, John (1979), "Sobre la determinación del género de un gráfico en pasos O (v O (g)) (Informe preliminar)", Proc. 11º año. Simposio ACM sobre teoría de la computación , págs. 27–37, doi : 10.1145/800135.804395.
10. Myrvold, Wendy ; Kocay, William (1 de marzo de 2011). "Errores en los algoritmos de incrustación de gráficos". 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