En teoría de grafos topológicos , un mapa o gema codificada por grafos es un método para codificar una incrustación celular de un gráfico utilizando un gráfico diferente con cuatro vértices por borde del gráfico original. [1] Es el análogo topológico de la runcinación , una operación geométrica sobre poliedros . Lins (1982) formuló y nombró mapas codificados en gráficos. [2] Los sistemas alternativos y equivalentes para representar incrustaciones celulares incluyen sistemas de rotación con signo y gráficos de cinta .
El mapa codificado en gráfico para un gráfico incrustado es otro gráfico cúbico junto con una coloración de 3 bordes de . Cada borde de se expande en exactamente cuatro vértices en , uno para cada elección de lado y punto final del borde. Un borde en conecta cada uno de esos vértices con el vértice que representa el lado opuesto y el mismo punto final de ; estos bordes están por convención coloreados en rojo. Otro borde conecta cada vértice con el vértice que representa el punto final opuesto y el mismo lado de ; estos bordes son, por convención, de color azul. Una arista del tercer color, amarillo, conecta cada vértice con el vértice que representa otra arista que se encuentra en el mismo lado y punto final. [1]
Una descripción alternativa de es que tiene un vértice para cada bandera de (una tripleta mutuamente incidente de un vértice, una arista y una cara). Si es una bandera, entonces hay exactamente un vértice , una arista y una cara tales que , y también son banderas. Los tres colores de bordes 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 gráficos de esta manera requiere más cuidado. Cuando aparece la misma cara a ambos lados de un borde, como puede suceder, por ejemplo, en el caso de una incrustación plana de un árbol , los dos lados dan lugar a diferentes vértices de gema. Y cuando aparece el mismo vértice en ambos extremos de un bucle automático , los dos extremos del borde nuevamente dan lugar a diferentes vértices de gema. De esta forma, cada triplete podrá estar asociado hasta con cuatro vértices diferentes de la gema. [1]
Siempre que un gráfico cúbico pueda tener tres bordes coloreados de modo que todos los ciclos rojo-azul de la coloración tengan una longitud de cuatro, el gráfico coloreado se puede interpretar como un mapa codificado por gráfico y representa una incrustación de otro gráfico . Para recuperar y su incrustación, interprete cada ciclo de 2 colores de como la cara de una incrustación de sobre una superficie , contraiga cada ciclo rojo-amarillo en un solo vértice de y reemplace cada par de bordes azules paralelos dejados por la contracción con un solo borde de . [1]
El gráfico dual de un mapa codificado en gráfico se puede obtener del mapa cambiándolo de color de modo que los bordes rojos de la gema se vuelvan azules y los bordes azules se vuelvan rojos. [3]
