| dbo:abstract
|
- 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. Es el análogo topológico de una , una operación geométrica sobre poliedros. Los mapas codificados en grafos fueron formulados y nombrados por . 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 es otro grafo cúbico junto con un de . Cada arista de se expande en exactamente cuatro vértices en , uno para cada opción de lado y el punto final de la arista. Una arista 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. Otro borde en 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. Una arista en del tercer color, amarillo, conecta cada vértice con el vértice que representa otra arista que se encuentra con en el mismo lado y punto final. Una descripción alternativa de es que tiene un vértice para cada bandera de (una triple incidencia mutua 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 los bordes en 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 podrá asociarse con hasta cuatro vértices diferentes del mapa de grafo codificado. Siempre que un grafo cúbico 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 . Para recuperar y su embebido, se debe interpretar cada ciclo de 2 colores de como la cara de una incrustación de 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 . 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. (es)
- In topological graph theory, a graph-encoded map or gem is a method of encoding a cellular embedding of a graph using a different graph with four vertices per edge of the original graph. It is the topological analogue of runcination, a geometric operation on polyhedra. Graph-encoded maps were formulated and named by .Alternative and equivalent systems for representing cellular embeddings include signed rotation systems and ribbon graphs. The graph-encoded map for an embedded graph is another cubic graph together with a 3-edge-coloring of . Each edge of is expanded into exactly four vertices in , one for each choice of a side and endpoint of the edge. An edge in connects each such vertex to the vertex representing the opposite side and same endpoint of ; these edges are by convention colored red. Another edge in connects each vertex to the vertex representing the opposite endpoint and same side of ; these edges are by convention colored blue. An edge in of the third color, yellow, connects each vertex to the vertex representing another edge that meets at the same side and endpoint. An alternative description of is that it has a vertex for each flag of (a mutually incident triple of a vertex, edge, and face). If is a flag,then there is exactly one vertex , edge , and face such that , , and are also flags. The three colors of edges in represent each of these three types of flags that differ by one of their three elements. However, interpreting a graph-encoded map in this way requires more care. When the same face appears on both sides of an edge, as can happen for instance for a planar embedding of a tree, the two sides give rise to different gem vertices. And when the same vertex appears at both endpoints of a self-loop, the two ends of the edge again give rise to different gem vertices. In this way, each triple may be associated with up to four different vertices of the gem. Whenever a cubic graph can be 3-edge-colored so that the red-blue cycles of the coloring all have length four, the colored graph can be interpreted as a graph-encoded map, and represents an embedding of another graph .To recover and its embedding, interpret each 2-colored cycle of as the face of an embedding of onto a surface,contract each red--yellow cycle into a single vertex of , and replace each pair of parallel blue edges left by the contraction with a single edge of . The dual graph of a graph-encoded map may be obtained from the map by recoloring it so that the red edges of the gem become blue and the blue edges become red. (en)
|