Incorporación de gráficos

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

En la teoría del gráfico topológico, una incrustaciones (también deletreado Imbedding) de un gráfico ${\displaystyle G.$ sobre una superficie ${\displaystyle \Sigma$ es una representación de ${\displaystyle G.$ on ${\displaystyle \Sigma$ en qué puntos ${\displaystyle \Sigma$ se asocian con vértices y arcos simples (imágenes homeomorfos de $[0,1]$ ) están asociados con bordes de tal manera que:

los puntos finales del arco asociado con un borde $e$ son los puntos asociados con los vértices finales $e,$
no arcs incluyen puntos asociados con otros vértices,
dos arcos nunca intersectan en un punto que es interior a cualquiera de los arcos.

Aquí una superficie es conectada $2$ - múltiples.

Informalmente, 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 sólo en sus puntos finales. Es bien sabido que cualquier gráfico finito puede ser incrustado en el espacio Euclideano tridimensional $\mathbb {R} } {}} {}displaystyle \mathbb {R}$ . Un gráfico plano es uno que puede ser incrustado en espacio Euclideano 2dimensional $\mathbb {R} ^{2$

A menudo, un incrustaciones se considera una clase de equivalencia (bajo homeomorfismos de ${\displaystyle \Sigma$ ) de las representaciones del tipo que 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 de los bordes. En tales contextos, la definición más estricta se describe como "incrustación de grafos sin cruces".

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

Terminología

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 bordes de ${\displaystyle G.$ es una familia de regiones (o caras). A Incrustación de 2 celdas, embedida celular o mapa es una incrustación en la que cada cara es homeomorfa a un disco abierto. A cierre de 2 celdas es una incrustación en la que el cierre de cada cara es homeomórfico a un disco cerrado.

El género de un gráfico es el número mínimo $n$ tal que el gráfico puede ser incrustado en una superficie del género $n$ . En particular, un gráfico plano tiene género $0$ , porque se puede dibujar en una esfera sin traicionar. Un gráfico que puede ser incrustado en un toro se llama un gráfico toroidal.

El genus no deseable de un gráfico es el número mínimo $n$ tal que el gráfico puede ser incrustado en una superficie no-orientable del género (no-orientable) $n$ .

El Euler genus de un gráfico es el número mínimo $n$ tal que el gráfico puede ser incrustado en una superficie orientable del género (orientable) $n/2$ o en una superficie no-orientable del género (no-orientable) $n$ . Un gráfico es orientablemente simple si El género Euler es más pequeño que su género no deseable.

El máximo género de un gráfico es el entero maximal $n$ tal que el gráfico puede ser $2$ -cel incrustado en una superficie orientable del género $n$ .

Combinatorial embedding

Un gráfico incrustado 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 sistema de rotación en sí mismo se denomina "incrustació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 ó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 "mitades de aristas" o "lados". Según esta convención, en todos los recorridos de límites de caras, cada mitad de arista se recorre solo una vez y las dos mitades 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 discos topológicos para los vértices y los bordes de un gráfico incrustado, y el mapa de gráficos codificados, un gráfico cúbico con bordes coloreados con cuatro vértices para cada borde del gráfico incrustado.

Computacional complejidad

El problema de encontrar el género gráfico es NP-hard (el problema de determinar si un $n$ - El grafito de versión tiene género $g$ es NP-complete).

Al mismo tiempo, el problema del género de grafos se puede manejar con parámetros fijos, es decir, se conocen algoritmos de tiempo polinomial para verificar si un grafo se puede incrustar 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 de I. Filotti y G.L. Miller y otro de John Reif. Sus planteamientos eran bastante diferentes, pero por sugerencia del comité del programa presentaron un trabajo conjunto. Sin embargo, Wendy Myrvold y William Kocay demostraron en 2011 que el algoritmo propuesto por Filotti, Miller y Reif era incorrecto.

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

Embeddings of graphs into higher-dimensional spaces

Se sabe que cualquier gráfico finito puede ser incorporado a un espacio tridimensional.

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 de 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 que sean coplanares. Por ejemplo, esto puede lograrse colocando el vértice i en el punto (i,i²,i³) de la curva de momentos.

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

Galería

El gráfico Petersen y el mapa asociado incrustado en el plano proyectivo. Puntos opuestos en el círculo se identifican produciendo una superficie cerrada del género no deseable 1.
El gráfico Pappus y el mapa asociado incrustado en el torus.
El gráfico de grado 7 Klein y el mapa asociado incrustados en una superficie orientable del género 3.

Véase también

Embedding, for other kinds of embeddings
Espesor del libro
Espesor de la moneda
Lista de bordes doblemente conectados, una estructura de datos para representar un gráfico en el plano
Mapa regular (teoría gráfica)
El teorema de Fáry, que dice que siempre es posible una incrustación planaria recta de un gráfico plano.
Triangulación (geometría)

Referencias

^ a b Cohen, Robert F.; Eades, Peter; Lin, Tao; Ruskey, Frank (1995), "Dibujo gráfico tridimensional", en Tamassia, Roberto; Tollis, Ioannis G. (eds.), Dibujo Gráfico: DIMACS International Workshop, GD '94 Princeton, New Jersey, USA, October 10–12, 1994, Proceedings, Lecture Notes in Computer Science, vol. 894, Springer, pp. 1–11, doi:10.1007/3-540-58950-3_351, ISBN 978-3-540-58950-1.
^ Katoh, Naoki; Tanigawa, Shin-ichi (2007), "Enumerating Constrained Non-crossing Geometric Spanning Trees", Computing and Combinatorics, 13th Annual International Conference, COCOON 2007, Banff, Canada, 16-19 de julio de 2007, Actas, Notas de conferencias en ciencias de la informática, vol. 4598, Springer-Verlag, págs. 243 a 253, CiteSeerX 10.1.1.483.874, doi:10.1007/978-3-540-73545-8_25, ISBN 978-3-540-73544-1.
^ a b Gross, Jonathan; Tucker, Thomas W. (2001), Gráfico Topológico Teoría, Dover Publications, ISBN 978-0-486-41741-7.
^ Lando, Sergei K.; Zvonkin, Alexander K. (2004), Gráficos sobre superficies y sus aplicaciones, Springer-Verlag, ISBN 978-3-540-00203-1.
^ 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, Notas de conferencia sobre informática, vol. 1858, Springer-Verlag, págs. 95 a 104, doi:10.1007/3-540-44968-X_10, ISBN 978-3-540-67787-1.
^ Didjev, Hristo N. (1995), "Al dibujar un gráfico convexly en el plano", Graph Drawing, DIMACS International Workshop, GD '94, Princeton, New Jersey, USA, 10–12, 1994, Proceedings, Lecture Notes in Computer Science, vol. 894, Springer-Verlag, pp. 76–83, doi:10.1007/3-540-58950-3_358, ISBN 978-3-540-58950-1.
^ Duncan, Christian; Goodrich, Michael T.; Kobourov, Stephen (2010), "Planar Drawings of Higher-Genus Graphs", Graph Drawing, 17th International Symposium, GD 2009, Chicago, IL, USA, 22-25 de septiembre de 2009, Documentos revisados, Notas de conferencia en informática, vol. 5849, Springer-Verlag, pp. 45–56, arXiv:0908.1608, doi:10.1007/978-3-642-11805-0_7, ISBN 978-3-642-11804-3.
^ Thomassen, Carsten (1989), "El problema del género gráfico es NP-complete", Journal of Algorithms, 10 (4): 568–576, doi:10.1016/0196-6774(89)90006-0
^ Filotti, I. S.; Miller, Gary L.; Reif, John (1979), "Al determinar el género de un gráfico en O(v O(g)) pasos(Informe preliminar)", Proc. 11th Annu. Simposio ACM sobre Teoría de la Computación, págs. 27 a 37, doi:10.1145/800135.804395.
^ Myrvold, Wendy; Kocay, William (1 de marzo de 2011). "Errores en Algoritmos Embedding de Gráficos". Journal of Computer and System Sciences. 2 (77): 430-438. doi:10.1016/j.jcss.2010.06.002.
^ Mohar, Bojan (1999), "Un algoritmo de tiempo lineal para insertar 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

Más resultados...