En la teoría de grafos topológicos , una incrustación (también deletreada incrustación ) de una gráfica en una superficie es una representación de en en que puntos de están asociados con vértices y arcos simples ( imágenes homeomórficas de) están asociados con los bordes de tal manera que:
- los puntos finales del arco asociado con una arista son los puntos asociados con los vértices finales de
- ningún arco incluye puntos asociados con otros vértices,
- dos arcos nunca se cruzan en un punto que es interior a cualquiera de los arcos.
Aquí una superficie es un compacto , conectado - colector .
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 cruzarse solo en sus puntos finales. Es bien sabido que cualquier gráfico finito se puede incrustar en el espacio euclidiano tridimensional.. [1] Un gráfico plano es aquel que se puede incrustar en un espacio euclidiano bidimensional.
A menudo, una incrustación se considera una clase de equivalencia (bajo homeomorfismos de) 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 gráficos" omitiendo la condición de no intersección para los bordes. En tales contextos, la definición más estricta se describe como "incrustación de gráficos no cruzados". [2]
Este artículo trata solo 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áfico " 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 rostro es homeomórfico 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 gráfico es el número entero mínimo.tal que el gráfico se pueda incrustar en una superficie de género . En particular, un gráfico plano tiene género, porque se puede dibujar en una esfera sin autocruzamiento. El género no orientable de un gráfico es el número entero mínimo tal que el gráfico se pueda incrustar en una superficie no orientable del género (no orientable) . [3]
El género Euler de un gráfico es el número entero mínimo tal que el gráfico se pueda incrustar en una superficie orientable del género (orientable) o en una superficie no orientable de género (no orientable) . Un gráfico es orientablemente simple si su género Euler es más pequeño que su género no orientable.
El género máximo de un gráfico es el número entero máximo tal que el gráfico pueda ser -célula incrustada en una superficie orientable del género .
Incrustación combinatoria
Un gráfico 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 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, el manejo de estos pedidos basados en caras es menos sencillo, ya que en algunos casos algunos bordes se pueden atravesar 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 borde se "divide" longitudinalmente en dos "medios bordes" o "lados". Según esta convención, en todos los recorridos de límites de caras, cada medio borde se atraviesa solo una vez y los dos medios bordes del mismo borde 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 bordes de un gráfico incrustado, y el mapa codificado por gráficos , 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 gráfico es NP-difícil (el problema de determinar si un-El gráfico de vértice tiene género es NP-completo ). [8]
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 ocurrió en 1979, cuando los algoritmos de complejidad temporal O ( n O ( g ) ) se presentaron de forma independiente al Simposio Anual de ACM sobre Teoría de la Computación : uno de I. Filotti y GL Miller y otro de 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 dado por Filotti, Miller y Reif era incorrecto. [10]
En 1999 se informó que el caso de género fijo puede resolverse 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 se puede incrustar 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 , y todos los semiplanos tienen esa línea como límite común. Una incrustación como esta en la que los bordes se dibujan en medios planos se denomina incrustación de libro del gráfico. Esta metáfora surge de imaginar que cada uno de los planos donde se dibuja un borde es como la página de un libro. Se observó que, de hecho, se pueden dibujar varios bordes en la misma "página"; el grosor del libro del gráfico es el número mínimo de medios planos necesarios para tal dibujo.
Alternativamente, cualquier gráfico finito se puede dibujar con bordes en línea recta en tres dimensiones sin cruces colocando sus vértices en posición general de modo que no haya cuatro coplanares. Por ejemplo, esto se puede lograr colocando el i- ésimo vértice en el punto ( i , i 2 , i 3 ) de la curva de momentos .
Una incrustación de un gráfico en un espacio tridimensional en el que no hay dos ciclos vinculados topológicamente se denomina incrustación sin enlace . Un gráfico tiene una incrustación sin enlaces si y solo si no tiene uno de los siete gráficos de la familia Petersen como menor .
Galería
El gráfico de Petersen y el mapa asociado incrustados en el plano proyectivo. Los puntos opuestos en el círculo se identifican produciendo una superficie cerrada del género 1 no orientable.
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 incrustados en una superficie orientable del género 3.
Ver también
- Incrustaciones , para otros tipos de incrustaciones
- Espesor del libro
- Espesor del gráfico
- Lista de bordes doblemente conectados , 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
- ↑ a b Cohen, Robert F .; Eades, Peter ; Lin, Tao; Ruskey, Frank (1995), "Dibujo gráfico tridimensional", en Tamassia, Roberto ; Tollis, Ioannis G. (eds.), Graph Drawing: DIMACS International Workshop, GD '94 Princeton, Nueva Jersey, EE. UU., 10 al 12 de octubre de 1994, Actas , Lecture Notes in Computer Science , 894 , Springer, págs. 1– 11, doi : 10.1007 / 3-540-58950-3_351 , ISBN 978-3-540-58950-1.
- ^ Katoh, Naoki; Tanigawa, Shin-ichi (2007), "Enumeración de árboles de expansión geométricos restringidos que no se cruzan", Computación y combinatoria, 13a Conferencia Internacional Anual, COCOON 2007, Banff, Canadá, 16-19 de julio de 2007, Actas , Notas de conferencias en Ciencias de la Computación , 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.
- ^ a b Gross, Jonathan; Tucker, Thomas W. (2001), Teoría de gráficos topológicos , Publicaciones de Dover, 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, 6ta Conferencia Internacional Anual, COCOON 2000, Sydney, Australia, 26-28 de julio de 2000, Actas , Lecture Notes in Computer Science, 1858 , Springer -Verlag, págs. 95-104, doi : 10.1007 / 3-540-44968-X_10 , ISBN 978-3-540-67787-1.
- ^ Didjev, Hristo N. (1995), "On drawing a graphly convexly in the plane", Graph Drawing, DIMACS International Workshop, GD '94, Princeton, Nueva Jersey, EE. UU., 10 al 12 de octubre de 1994, Actas , Notas de conferencias en Ciencias de la computación, 894 , Springer-Verlag, págs. 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, Revised Papers , Lecture Notes in Computer Science, 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.
- ^ 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
- ^ Filotti, IS; 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. 11th Annu. Simposio ACM sobre teoría de la computación , págs. 27–37, doi : 10.1145 / 800135.804395.
- ^ Myrvold, Wendy ; Kocay, William (1 de marzo de 2011). "Errores en algoritmos de incrustación de gráficos". Revista de Ciencias de la Computación y Sistemas . 2 (77): 430–438. doi : 10.1016 / j.jcss.2010.06.002 .
- ^ 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