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] Los sistemas alternativos y equivalentes para representar embebidos celulares incluyen a los sistemas de rotación y a los grafos de cinta con signo.
se expande en exactamente cuatro vértices en
conecta cada vértice con el vértice que representa el lado opuesto y el mismo extremo de
Estos bordes son por convención de color rojo.
conecta cada vértice con el vértice que representa el extremo opuesto y el mismo lado de
; estos bordes son por convención de color azul.
del tercer color, amarillo, conecta cada vértice con el vértice que representa otra arista
en el mismo lado y punto final.
es que tiene un vértice para cada bandera de
(una triple incidencia mutua de un vértice, una arista y una cara).
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.
podrá asociarse con hasta cuatro vértices diferentes del mapa de grafo codificado.
en una superficie, contrayendo cada ciclo rojo-amarillo en un solo vértice de
, y reemplazando cada par de bordes azules paralelos dejados por la contracción con un solo borde de
[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.
