Grafo embebido

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

• Los extremos del arco asociado a un lado ${\displaystyle e}$ son los puntos asociados a los vértices extremos de ${\displaystyle e}$
• Ningún arco incluye puntos asociados a otros vértices
• Dos arcos nunca se cortan en un punto interior a cualquiera de los arcos

El grafo de Heawood y el mapa asociado embebido en un toro

Aquí se entiende por superficie una variedad de orden ${\displaystyle 2}$ compacta y conexa.

De manera informal, un embebido de un gráfico en una superficie es un dibujo del gráfico en la superficie de tal manera que sus lados se intersequen solo en sus puntos extremos. Es bien sabido que cualquier gráfico finito se puede incrustar en el espacio euclídeo tridimensional ${\displaystyle \mathbb {R} ^{3}}$.^[1] Por definición, un grafo plano es aquel que se puede incrustar en un espacio euclídeo bidimensional ${\displaystyle \mathbb {R} ^{2}.}$

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

Algunos autores definen una versión más débil de la definición de "embebido de grafos" al omitir la condición de no intersección para los lados. En tales contextos, la definición más estricta se describe como embebido de grafos sin cruces.^[2]

Este artículo trata solo de la definición estricta de embebido de grafos. La definición más débil se discute en los artículos "dibujo de grafos" y "número de cruce".

Terminología

Si un grafo ${\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 un embebido en el que cada cara es homeomorfa a un disco abierto.^[4] Una incrustación cerrada de 2 celdas es un embebido en el que el cierre de cada cara es homeomorfo a un disco cerrado.

El género (o también genus) de un Grafo es el número entero mínimo ${\displaystyle n}$ tal que el gráfico se puede embeber en una superficie de genus ${\displaystyle n}$. En particular, un grafo plano tiene el género ${\displaystyle 0}$ porque se puede dibujar en una esfera sin autocruzarse. El género no orientable de un grafo es el número entero mínimo ${\displaystyle n}$ tal que el grafo en cuestión se puede embeber en una superficie no orientable de género (no orientable) ${\displaystyle n}$.^[3]

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

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

Embebido combinatorio

Artículo principal: Sistema de rotación

Un grafo embebido define de forma única órdenes cíclicos de aristas incidentes en el mismo vértice. El conjunto de todas estas ordenaciones cíclicas se llama sistema de rotación. Las incrustaciones con el mismo sistema de rotación se consideran equivalentes y la clase de embebidos de equivalencia correspondiente se denomina embebido combinatorio (a diferencia del término embebido topológico, 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 embebido combinatorio.^[5][6][7]

Un grafo incrustado también define órdenaciones cíclicas naturales de lados 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 algunos bordes pueden atravesarse dos veces en un límite de cara. Por ejemplo, este es siempre el caso de embebidos de árboles, que tienen una sola cara. Para superar este inconveniente combinatorio, se puede considerar que cada lado está dividido longitudinalmente en dos medios lados o bordes. Según esta convención, en todos los recorridos de límites de caras, cada medio lado se recorre solo una vez y los dos medios lados del mismo lado siempre se recorren en direcciones opuestas.

Otras representaciones equivalentes de embebidos celulares incluyen a los grafos de cinta, un espacio topológico formado al pegar juntos discos topológicos para los vértices y los lados de un gráfico embebido, y a los mapas de grafos codificados, un grafo cúbico de color de borde con cuatro vértices para cada borde del gráfico incrustado.

Complejidad computacional

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

Al mismo tiempo, el problema del género del gráfico es de complejidad parametrizada, es decir, se sabe que algoritmos de complejidad temporal polinómica verifican si un gráfico se puede embeber 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 dos algoritmos de complejidad temporal O(n^O(g)) fueron presentados de forma independiente al Simposio de la ACM sobre Teoría de la Computación: uno por I. Filotti y G.L. Miller y otro por John Reif. Sus enfoques fueron 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 propuesto por Filotti, Miller y Reif era incorrecto.^[10]

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

Embebidos de grafos en espacios de mayor dimensión

Se sabe que cualquier grafo finito se puede incrustar en un espacio tridimensional.^[1]

Un método para hacerlo es colocar los puntos en cualquier línea recta en el espacio y dibujar los lados como curvas, cada una de las cuales se encuentra en un semiespacio distinto, con todos los semiplanos teniendo esa línea como límite común. Una incrustación como esta en la que los bordes se dibujan en semiplanos se llama embebido en libro del grafo. 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 varios vínculos 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 se puede dibujar con vínculos rectilíneos en tres dimensiones sin cruces colocando sus vértices en posición general para que no haya cuatro coplanarios. Por ejemplo, esto se puede lograr colocando el vértice i en el punto (i,i²,i³) de una curva de momentos.

Un embebidp de un gráfico en un espacio tridimensional en el que dos de los ciclos no están vinculados topológicamente se denomina embebido sin enlaces. Un grafo tiene un embebido sin enlaces si y solo si no incluye uno de los siete grafos de la familia de Petersen como menor.

Galería

• 
  El grafo de Petersen y su embebido asociado en el plano proyectivo. Los puntos opuestos en el círculo se identifican dando como resultado una superficie cerrada de género 1 no orientable
• 
  El grafo de Papo y su aplicación asociada embebida en un toro
• 
  El grafo de Klein de grado 7 y su aplicación asociada incrustada en una superficie orientable de género 3

Véase también

• Encaje, para otro tipo de embebidos
• Embebido en libro
• Espesor (teoría de grafos)
• Lista de aristas doblemente conectadas, una estructura de datos para representar un gráfico embebido en un plano
• Mapa regular (teoría de grafos)
• Teorema de Fáry, que afirma que siempre es posible obtener un embebido en una línea recta de un grafo plano
• Triangulación

Referencias

1. Cohen, Robert F.; Eades, Peter; Lin, Tao; Ruskey, Frank (1995), «Three-dimensional graph drawing», en Tamassia, Roberto; Tollis, Ioannis G., eds., Graph Drawing: DIMACS International Workshop, GD '94 Princeton, New Jersey, USA, October 10–12, 1994, Proceedings, Lecture Notes in Computer Science 894, Springer, pp. 1-11, ISBN 978-3-540-58950-1, doi:10.1007/3-540-58950-3_351..
2. Katoh, Naoki; Tanigawa, Shin-ichi (2007), «Enumerating Constrained Non-crossing Geometric Spanning Trees», Computing and Combinatorics, 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007, Proceedings, Lecture Notes in Computer Science 4598, Springer-Verlag, pp. 243-253, ISBN 978-3-540-73544-1, doi:10.1007/978-3-540-73545-8_25, «citeseerx: 10.1.1.483.874»..
3. Gross, Jonathan; Tucker, Thomas W. (2001), Topological Graph Theory, Dover Publications, ISBN 978-0-486-41741-7..
4. Lando, Sergei K.; Zvonkin, Alexander K. (2004), Graphs on Surfaces and their Applications, 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, July 26–28, 2000, Proceedings, Lecture Notes in Computer Science 1858, Springer-Verlag, pp. 95-104, ISBN 978-3-540-67787-1, doi:10.1007/3-540-44968-X_10..
6. Didjev, Hristo N. (1995), «On drawing a graph convexly in the plane», Graph Drawing, DIMACS International Workshop, GD '94, Princeton, New Jersey, USA, October 10–12, 1994, Proceedings, Lecture Notes in Computer Science 894, Springer-Verlag, pp. 76-83, ISBN 978-3-540-58950-1, doi:10.1007/3-540-58950-3_358..
7. Duncan, Christian; Goodrich, Michael T.; Kobourov, Stephen (2010), «Planar Drawings of Higher-Genus Graphs», Graph Drawing, 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers, Lecture Notes in Computer Science 5849, Springer-Verlag, pp. 45-56, ISBN 978-3-642-11804-3, arXiv:0908.1608, doi:10.1007/978-3-642-11805-0_7..
8. Thomassen, Carsten (1989), «The graph genus problem is NP-complete», Journal of Algorithms 10 (4): 568-576, doi:10.1016/0196-6774(89)90006-0.
9. Filotti, I. S.; Miller, Gary L.; Reif, John (1979), «On determining the genus of a graph in O(v O(g)) steps(Preliminary Report)», Proc. 11th Annu. ACM Symposium on Theory of Computing, pp. 27-37, doi:10.1145/800135.804395..
10. Myrvold, Wendy; Kocay, William (1 de marzo de 2011). «Errors in Graph Embedding Algorithms». Journal of Computer and System Sciences 2 (77): 430–438. doi:10.1016/j.jcss.2010.06.002.
11. Mohar, Bojan (1999), «A linear time algorithm for embedding graphs in an arbitrary surface», SIAM Journal on Discrete Mathematics 12 (1): 6-26, doi:10.1137/S089548019529248X, «citeseerx: 10.1.1.97.9588».

• Datos: Q5597085