Incrustación de gráficos

Una incrustación de gráficos es una representación de un gráfico en una superficie determinada estudiada en el marco de la teoría de gráficos topológicos , en la que los puntos están asociados con los vértices del gráfico y los arcos simples ( imágenes homeomórficas [0,1]) en la superficie están asociados con los bordes del gráfico . de una manera que: $GRAMO$ $\Sigma$ $\Sigma$

los extremos de un arco asociado con un borde del gráfico son los puntos asociados con los extremos de ese borde del gráfico $mi$ $mi$
ningún arco contiene puntos asociados con otros vértices
no hay dos arcos que se crucen en los puntos interiores de esos arcos.

Aquí la superficie es una variedad compacta de 2 conectados .

De manera informal, una incrustación de un gráfico en una superficie es una imagen del gráfico en la superficie de tal manera que sus bordes solo pueden cruzarse en los puntos finales. Es bien sabido que cualquier gráfico finito puede estar incrustado en un espacio euclidiano tridimensional [1] , y los gráficos planos pueden estar incrustados en un espacio euclidiano bidimensional . $\mathbb{R} ^{3}$ $\matemáticas {R} ^{2}$

A menudo, una incrustación se ve como una clase de equivalencia (mediante homeomorfismos ) de representaciones del tipo descrito. $\Sigma$

En el contexto de los problemas de visualización de gráficos, también se considera una versión débil de la definición de incrustación de gráficos, en la que no se requiere la ausencia de intersecciones de bordes. En consecuencia, la definición fuerte se describe como "una incrustación de un gráfico sin intersecciones" [2] .

Terminología

Si el grafo está incrustado en una superficie cerrada , entonces el complemento de la unión de puntos y arcos asociados a los vértices y aristas del grafo es una familia de una familia de regiones (o caras) [3] . Una incrustación o mapa de celda bidimensional es una incrustación en la que cada cara es homeomorfa a un disco abierto [4] . Una incrustación de celda cerrada bidimensional es una incrustación en la que el cierre de cualquier cara es homeomorfo a un disco cerrado. $GRAMO$ $\Sigma$ $GRAMO$

El apilamiento de gráficos se usa a menudo como sinónimo de anidamiento, especialmente en el caso de gráficos planos.

El género de un gráfico es el entero más pequeño tal que el gráfico se puede incrustar en la superficie del género . En particular, un gráfico plano tiene género 0 porque se puede dibujar en una esfera sin autointersecciones. El género no orientable de un gráfico es el entero más pequeño tal que el gráfico se puede incrustar en una superficie no dirigida de género (no orientable) [3] . $norte$ $norte$ $norte$ $norte$

El género de Euler de un gráfico es el entero más pequeño tal que el gráfico se puede incrustar en una superficie orientable de género (orientable) o una superficie no dirigida de género (no orientable) . Un grafo es simplemente orientable si su género de Euler es menor que su género no orientable. $norte$ ${\tfrac{n}{2))$ $norte$

El género máximo de un gráfico es el entero máximo tal que el gráfico se puede incrustar en celda plana (la incrustación es de celda plana si cualquier curva cerrada que no intersecta los bordes del gráfico se contrae en un punto) en una superficie orientable del género _ $norte$ $norte$

Incrustación combinatoria

Un gráfico anidado define de forma única los órdenes cíclicos de las aristas incidentes en el mismo vértice. El conjunto de todos estos órdenes cíclicos se denomina sistema circular . Las incrustaciones con el mismo sistema circular se consideran equivalentes, y la clase de incrustaciones de equivalencia correspondiente se denomina incrustación combinatoria (a diferencia del término incrustación topológica , que se refiere a la definición anterior de puntos y curvas). A veces, un sistema circular en sí mismo se denomina "incrustación combinatoria" [5] [6] [7] .

El gráfico anidado también define órdenes de bordes cíclicos naturales que definen los límites de las caras anidadas. Sin embargo, trabajar con estos órdenes orientados a facetas es menos obvio, ya que en algunos casos algunos bordes pueden atravesarse dos veces al atravesar el límite de una cara. Por ejemplo, esto siempre es cierto cuando se anidan árboles que tienen un solo borde. Para superar este obstáculo combinatorio, se puede considerar que cada borde está "dividido" en dos "medios bordes" o "lados". Según estas convenciones, en todas las caras, el límite atraviesa cada semiarista solo una vez, y cada semiarista de una arista siempre se recorre en direcciones opuestas.

Complejidad computacional

El problema de determinar el género de un grafo es NP-completo (el problema de determinar si un grafo con vértices tiene género es NP-completo ) [8] . $norte$ $gramo$

Al mismo tiempo, el problema de determinar el género de un gráfico es fijo-paramétricamente solucionable , es decir, se conocen algoritmos con tiempo polinomial para verificar si un gráfico se puede incrustar en una superficie con un género dado. Lo mismo es cierto para encontrar un archivo adjunto.

El primer avance se produjo en 1979 , cuando los algoritmos de complejidad temporal se informaron de forma independiente en el Simposio anual de ACM sobre teoría computacional , uno propuesto por Ion Filotti y Gary Miller y otro por John Reif . Sus enfoques eran completamente diferentes, pero a sugerencia del comité organizador, presentaron un artículo fusionado [9] . $O(n^{O(g)})$

En 1999, se demostró que el caso de género fijo se puede resolver en tiempo lineal en tamaño de gráfico y en tiempo doble exponencial en género [10] .

Incrustación de un gráfico en espacios de mayores dimensiones

Se sabe que cualquier gráfico finito se puede incrustar en un espacio tridimensional [1] .

Un método para tal incrustación es colocar puntos (vértices del gráfico) en una línea y dibujar los bordes como curvas que se encuentran en semiplanos separados que tienen esta línea como límite común a todos los semiplanos. Este tipo de incrustación se denomina incrustación de libro de gráficos . Esta metáfora se vuelve clara si imaginamos cada semiplano como una página de un libro. Está claro que algunos bordes se pueden dibujar sin intersecciones en la misma "página". El grosor de libro de un gráfico es el número mínimo de semiplanos en un libro incrustado.

Por otro lado, cualquier gráfico finito se puede dibujar sin intersecciones en un espacio tridimensional con bordes rectos colocando los vértices en una posición general tal que no hay cuatro coplanares (no se encuentran en el mismo plano). Por ejemplo, esto se puede lograr colocando el -ésimo vértice en un punto de la curva de momento . $i$ ${\ estilo de visualización (i, i ^ {2}, i ^ {3})}$

Una incrustación de un gráfico en un espacio tridimensional en el que no hay dos ciclos topológicamente vinculados se denomina incrustación no vinculada . Un gráfico tiene una incrustación no vinculada si y sólo si no contiene ninguno de los siete gráficos de la familia Peterson como menor .

Véase también

Lista de aristas doblemente enlazada : una estructura de datos para representar un gráfico incrustado en un plano
tarjeta correcta
El teorema de Fari , que establece que siempre hay una incrustación en el plano de un gráfico plano en el que todos los arcos están representados por segmentos de línea.

Notas

↑ 1 2 Cohen, Eades, Lin, Ruskey, 1995 , p. 1–11.
↑ Katoh, Tanigawa, 2007 , pág. 243–253.
↑ 12 Gross , Tucker, 2001 .
↑ Zvonkin, Lando, 2010 .
↑ Mutzel, Weiskircher, 2000 , pág. 95–104.
↑ Didjev, 1995 , pág. 76–83.
↑ Duncan, Goodrich, Kobourov, 2010 , pág. 45–56.
↑ Thomassen, 1989 , pág. 568–576.
↑ Filotti, Miller, Reif, 1979 , pág. 27–37.
↑ Mohar, 1999 , pág. 6–26.

Literatura

Robert F. Cohen, Peter Eades, Tao Lin, Frank Ruskey. Dibujo gráfico: Taller internacional DIMACS, GD '94 Princeton, Nueva Jersey, EE. UU., 10 al 12 de octubre de 1994, Actas / Roberto Tamassia, Ioannis G. Tollis. - Springer, 1995. - T. 894. - S. 1-11. — ( Apuntes de clase en informática ). -doi : 10.1007 / 3-540-58950-3_351 .
Petra Mutzel, René Weiskircher. 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. - Springer-Verlag, 2000. - T. 1858. - S. 95–104. — (Apuntes de clase en informática). - ISBN 978-3-540-67787-1 . -doi : 10.1007 / 3-540-44968-X_10 .
Christo N. Didjev. Dibujo gráfico, Taller internacional DIMACS, GD '94, Princeton, Nueva Jersey, EE. UU., 10 al 12 de octubre de 1994, Actas . - Springer-Verlag, 1995. - T. 894. - S. 76–83. — (Apuntes de clase en informática). -doi : 10.1007 / 3-540-58950-3_358 .
Christian Duncan, Michael T. Goodrich, Stephen Kobourov. Planor Drawings of Higher-Genus Graphs // Graph Drawing, 17th International Symposium, GD 2009, Chicago, IL, EE. UU., 22-25 de septiembre de 2009, Documentos revisados . - Springer-Verlag, 2010. - T. 5849. - S. 45-56. — (Apuntes de clase en informática). — ISBN 978-3-642-11804-3 . -doi : 10.1007 / 978-3-642-11805-0_7 .
Carsten Thomassen. El problema del género gráfico es NP-completo // Journal of Algorithms. - 1989. - T. 10 , núm. 4 . — S. 568–576 . - doi : 10.1016/0196-6774(89)90006-0 .
IS Filotti, Gary L. Miller, John Reif. Al determinar el género de un gráfico en O(v O(g)) pasos(Informe Preliminar) // Proc. 11º Anu. Simposio ACM sobre Teoría de la Computación . - 1979. - S. 27-37. -doi : 10.1145/ 800135.804395 .
Bojan Mohar. Un algoritmo de tiempo lineal para incrustar gráficos en una superficie arbitraria // SIAM Journal on Discrete Mathematics . - 1999. - T. 12 , núm. 1 . — Pág. 6–26 . -doi : 10.1137/ S089548019529248X .
Jonathan Gross, Thomas W. Tucker. Teoría de grafos topológicos . - Publicaciones de Dover, 2001. - ISBN 0-486-41741-7 .
A. K. Zvonkin, S. K. Lando. Gráficos sobre superficies y sus aplicaciones. - M. : MTSNMO, 2010. - ISBN 978-5-94057-588-7 .
Naoki Katoh, Shin-ichi Tanigawa. Enumeración de árboles de expansión geométricos no cruzados restringidos // Informática y combinatoria, 13.ª Conferencia internacional anual, COCOON 2007, Banff, Canadá, 16-19 de julio de 2007, Actas. - Springer-Verlag, 2007. - T. 4598. - S. 243-253. — ( Apuntes de clase en informática ). — ISBN 978-3-540-73544-1 . -doi : 10.1007 / 978-3-540-73545-8_25 .