Mapa de grafo codificado

En teoría de grafos topológica, un mapa de grafo codificado o GEM (por las iniciales de su nombre en inglés: Graph Encoded Map) es un método para codificar un embebidocelular de un grafo usando un grafo diferente con cuatro vértices por vínculo a partir del grafo original.^[1] Es el análogo topológico de una runcinación, una operación geométrica sobre poliedros. Los mapas codificados en grafos fueron formulados y nombrados por Lins (1982).^[2]

Un mapa de grafo codificado (triángulos grises y bordes coloreados) de un grafo en el plano (círculos blancos y bordes negros)

Los sistemas alternativos y equivalentes para representar embebidos celulares incluyen a los sistemas de rotación y a los grafos de cinta con signo.

El mapa de un grafo codificado para un grafo embebido ${\displaystyle G}$ es otro grafo cúbico ${\displaystyle H}$ junto con un 3-coloreado de aristas de ${\displaystyle H}$. Cada arista ${\displaystyle e}$ de ${\displaystyle G}$ se expande en exactamente cuatro vértices en ${\displaystyle H}$, uno para cada opción de lado y el punto final de la arista. Una arista en ${\displaystyle H}$ conecta cada vértice con el vértice que representa el lado opuesto y el mismo extremo de ${\displaystyle e}$. Estos bordes son por convención de color rojo. Otro borde en ${\displaystyle H}$ conecta cada vértice con el vértice que representa el extremo opuesto y el mismo lado de ${\displaystyle e}$; estos bordes son por convención de color azul. Una arista en ${\displaystyle H}$ del tercer color, amarillo, conecta cada vértice con el vértice que representa otra arista ${\displaystyle e'}$ que se encuentra con ${\displaystyle e}$ en el mismo lado y punto final. ^[1]

Una descripción alternativa de ${\displaystyle H}$ es que tiene un vértice para cada bandera de ${\displaystyle G}$ (una triple incidencia mutua de un vértice, una arista y una cara). Si ${\displaystyle (v,e,f)}$ es una bandera, entonces hay exactamente un vértice ${\displaystyle v'}$, una arista ${\displaystyle e'}$ y una cara ${\displaystyle f'}$ tales que ${\displaystyle (v',e,f)}$, ${\displaystyle (v,e',f)}$ y ${\displaystyle (v,e,f')}$ también son banderas. Los tres colores de los bordes en ${\displaystyle H}$ representan cada uno de estos tres tipos de banderas que se diferencian por uno de sus tres elementos. Sin embargo, interpretar un mapa codificado en grafos de esta manera requiere más cuidado. Cuando aparece la misma cara a ambos lados de una arista, como puede ocurrir, por ejemplo, con un embebido plano de un árbol, los dos lados dan lugar a diferentes vértices del GEM. Y cuando el mismo vértice aparece en ambos extremos de un bucle, los dos extremos de la arista nuevamente dan lugar a diferentes vértices del GEM. De esta forma, cada tripleta ${\displaystyle (v,e,f)}$ podrá asociarse con hasta cuatro vértices diferentes del mapa de grafo codificado.^[1]

Siempre que un grafo cúbico ${\displaystyle H}$ pueda tener 3 colores de borde, de modo que los ciclos rojo-azul del coloreado tengan una longitud de cuatro, el grafo coloreado puede interpretarse como un mapa de grafo codificado y representa un embebido de otro grafo ${\displaystyle G}$.

Para recuperar ${\displaystyle G}$ y su embebido, se debe interpretar cada ciclo de 2 colores de ${\displaystyle H}$ como la cara de una incrustación de ${\displaystyle H}$ en una superficie, contrayendo cada ciclo rojo-amarillo en un solo vértice de ${\displaystyle G}$, y reemplazando cada par de bordes azules paralelos dejados por la contracción con un solo borde de ${\displaystyle G}$.^[1]

El grafo dual de un mapa de grafo codificado se puede obtener del mapa cambiándolo de color para que los bordes rojos del GEM se vuelvan azules y los bordes azules se vuelvan rojos.^[3]

Referencias

1. Bonnington, C. Paul; Little, Charles H. C. (1995), The foundations of topological graph theory, New York: Springer-Verlag, p. 31, ISBN 0-387-94557-1, MR 1367285, doi:10.1007/978-1-4612-2540-9.
2. Lins, Sóstenes (1982), «Graph-encoded maps», Journal of Combinatorial Theory, Series B 32 (2): 171-181, MR 657686, doi:10.1016/0095-8956(82)90033-8.
3. Bonnington y Little (1995), pp. 111–112.

• Datos: Q48999823