En la teoría de grafos topológicos , un mapa o gema codificada por grafos es un método de codificación de una incrustación celular de un grafo utilizando un grafo diferente con cuatro vértices por arista del grafo original. [1] Es el análogo topológico de la runcinación , una operación geométrica sobre poliedros . Los mapas codificados por grafos fueron formulados y nombrados por Lins (1982). [2] Los sistemas alternativos y equivalentes para representar incrustaciones celulares incluyen sistemas de rotación con signo y grafos de cinta .
El mapa codificado por gráfico para un gráfico incrustado es otro gráfico cúbico junto con una coloración de 3 aristas de . Cada arista de se expande en exactamente cuatro vértices en , uno para cada elección de un lado y punto final de la arista. Una arista en conecta cada uno de esos vértices con el vértice que representa el lado opuesto y el mismo punto final de ; estas aristas están coloreadas por convención en rojo. Otra arista en conecta cada vértice con el vértice que representa el punto final opuesto y el mismo lado de ; estas aristas están coloreadas por convención en azul. Una arista en 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 (un triple mutuamente incidente de un vértice, arista y cara). Si es una bandera, entonces hay exactamente un vértice , arista y cara tal que , y también son banderas. Los tres colores de las aristas en representan cada uno de estos tres tipos de banderas que difieren en uno de sus tres elementos. Sin embargo, interpretar un mapa codificado en grafos de esta manera requiere más cuidado. Cuando la misma cara aparece en ambos lados de una arista, como puede suceder por ejemplo para una incrustación plana de un árbol , los dos lados dan lugar a diferentes vértices de gema. Y cuando el mismo vértice aparece en ambos puntos finales de un bucle propio , los dos extremos de la arista dan lugar nuevamente a diferentes vértices de gema. De esta manera, cada triple puede estar asociado con hasta cuatro vértices diferentes de la gema. [1]
Siempre que un gráfico cúbico pueda tener 3 aristas de color de modo que todos los ciclos rojo-azul de la coloración tengan una longitud de cuatro, el gráfico coloreado puede interpretarse como un mapa codificado por gráficos 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 único vértice de , y reemplace cada par de aristas azules paralelas que quede por la contracción con una única arista de . [1]
El gráfico dual de un mapa codificado por gráficos se puede obtener a partir 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]
