Incrustaciones de grafos

En la teoría topológica de grafos , una incrustación (también escrita como imbedding ) de un grafo en una superficie es una representación de en la que los puntos de se asocian con vértices y los arcos simples ( imágenes homeomórficas de ) se asocian con aristas de tal manera que:${\displaystyle G}$${\displaystyle \Sigma }$${\displaystyle G}$${\displaystyle \Sigma }$${\displaystyle \Sigma }$${\displaystyle [0,1]}$

• Los puntos extremos del arco asociado a una arista son los puntos asociados a los vértices extremos de${\displaystyle e}$${\displaystyle e,}$
• Ningún arco incluye puntos asociados a otros vértices,
• Dos arcos nunca se intersecan en un punto que sea interior a cualquiera de los arcos.

Aquí una superficie es una variedad conectada .${\displaystyle 2}$

De manera informal, una incrustación de un grafo en una superficie es un dibujo del grafo sobre la superficie de tal forma que sus aristas solo se intersecan en sus extremos. Es bien sabido que cualquier grafo finito puede incrustarse en el espacio euclidiano tridimensional . ^{[ 1 ]} Un grafo planar es aquel que puede incrustarse en el 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 se acaba de describir.${\displaystyle \Sigma }$

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 para las aristas. En tales contextos, la definición más estricta se describe como "incrustación de grafos sin cruces". ^{[ 2 ]}

Este artículo se centra únicamente en la definición estricta de incrustación de grafos. La definición menos estricta se analiza en los artículos " Dibujo de grafos " y " Número de cruces ".

Si un grafo está incrustado en una superficie cerrada , el complemento de la unión de los puntos y arcos asociados con 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 grafo es el entero mínimo tal que el grafo puede incrustarse en una superficie de género . En particular, un grafo planar tiene género , porque puede dibujarse en una esfera sin autocruzarse. Un grafo que puede incrustarse en un toro se denomina grafo toroidal .${\displaystyle n}$${\displaystyle n}$${\displaystyle 0}$

El género no orientable de un grafo es el entero mínimo tal que el grafo puede incrustarse en una superficie no orientable de género (no orientable) . ^{[ 3 ]}${\displaystyle n}$${\displaystyle n}$

El género de Euler de un grafo es el entero mínimo tal que el grafo puede incrustarse 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 de Euler es menor que su género no orientable.${\displaystyle n}$${\displaystyle n/2}$${\displaystyle n}$

El género máximo de un grafo es el entero máximo tal que el grafo puede incrustarse en -celdas en una superficie orientable de género .${\displaystyle n}$${\displaystyle 2}$${\displaystyle n}$

Un grafo 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 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). En ocasiones, el propio sistema de rotación se denomina "incrustación combinatoria". ^{[ 5 ] [ 6 ] [ 7 ]}

Un grafo incrustado también define órdenes cíclicas naturales de aristas que constituyen los límites de las caras de la incrustación. Sin embargo, manejar estos órdenes basados ​​en caras es menos sencillo, ya que en algunos casos algunas aristas pueden recorrerse dos veces a lo largo del límite de una cara. Por ejemplo, esto siempre ocurre en las incrustaciones de árboles, que tienen una sola cara. Para superar este inconveniente combinatorio, se puede considerar que cada arista se "divide" longitudinalmente en dos "semiaristas" o "lados". Bajo esta convención, en todos los recorridos de los límites de las caras, cada semiarista se recorre solo una vez y las dos semiaristas de la misma arista siempre se recorren en direcciones opuestas.

Other equivalent representations for cellular embeddings include the ribbon graph, a topological space formed by gluing together topological disks for the vertices and edges of an embedded graph, and the graph-encoded map, an edge-colored cubic graph with four vertices for each edge of the embedded graph.

The problem of finding the graph genus is NP-hard (the problem of determining whether an ${\displaystyle n}$-vertex graph has genus ${\displaystyle g}$ is NP-complete).^[8]

At the same time, the graph genus problem is fixed-parameter tractable, i.e., polynomial time algorithms are known to check whether a graph can be embedded into a surface of a given fixed genus as well as to find the embedding.

The first breakthrough in this respect happened in 1979, when algorithms of time complexityO(n^O(g)) were independently submitted to the Annual ACM Symposium on Theory of Computing: one by I. Filotti and G.L. Miller and another one by John Reif. Their approaches were quite different, but upon the suggestion of the program committee they presented a joint paper.^[9] However, Wendy Myrvold and William Kocay proved in 2011 that the algorithm given by Filotti, Miller and Reif was incorrect.^[10]

In 1999 it was reported that the fixed-genus case can be solved in time linear in the graph size and doubly exponential in the genus.^[11]

It is known that any finite graph can be embedded into a three-dimensional space.^[1]

One method for doing this is to place the points on any line in space and to draw the edges as curves each of which lies in a distinct halfplane, with all halfplanes having that line as their common boundary. An embedding like this in which the edges are drawn on halfplanes is called a book embedding of the graph. This metaphor comes from imagining that each of the planes where an edge is drawn is like a page of a book. It was observed that in fact several edges may be drawn in the same "page"; the book thickness of the graph is the minimum number of halfplanes needed for such a drawing.

Alternativamente, cualquier grafo finito puede dibujarse con aristas rectas en tres dimensiones sin cruces colocando sus vértices en una posición general de manera que no haya cuatro coplanares. Por ejemplo, esto puede lograrse colocando el i -ésimo vértice en el punto ( i , i2 , i3 ⁾ de la curva de ^momento .

Una incrustación de un grafo en un espacio tridimensional en la que ningún par de ciclos están vinculados topológicamente se denomina incrustación sin enlaces . Un grafo tiene una incrustación sin enlaces si y solo si no tiene como menor ninguno de los siete grafos de la familia de Petersen .

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

• Incrustación , para otros tipos de incrustaciones
• Grosor del libro
• Grosor del gráfico
• Lista de aristas doblemente conectadas , una estructura de datos para representar una incrustación de grafo en el plano
• Mapa regular (teoría de grafos)
• El teorema de Fáry , que establece que siempre es posible una incrustación planar en línea recta de un grafo planar.
• Triangulación (geometría)