De acuerdo con el libro Topological Graph Theory de Gross y Tucker, dada una incrustación celular de un gráfico en una superficie (por 'superficie' me refiero aquí a una esfera con algunos asas, y debajo de refiere a la esfera con exactamente tiradores), se puede definir un multigrafo dual tratando las caras de la incrustación del gráfico original como vértices y agregando un borde entre dos vértices para cada lado que las caras correspondientes tienen en común en el gráfico original.S n n
Aquí está mi problema . Dado un grafo , necesito encontrar otro gráfico tal que existe una superficie y una incrustación celular de en tal que es el doble de esta incrustación de . Sé que hay muchos gráficos posibles ; Sólo tengo que encontrar uno para cada gráfica .G ′ S G S G ′ G G ′ G
Tengo varias preguntas . Mi estrategia actual es (1) determinar el género de , (2) encontrar una incrustación de en y (3) encontrar el dual de esta incrustación. Todos esos pasos tienen algoritmos conocidos (aunque (1) es NP-Hard). Me pregunto si hay una manera de encontrar una que evite el cálculo del género, ya que ese es el cuello de botella de este enfoque, y esa es mi primera pregunta. Mi segunda pregunta es: si sé que es regular, ¿eso puede facilitar el cálculo del género? Y mi tercera pregunta es una solicitud de referencias que puedan ayudarme a resolver este problema.G G S n G ′ G
Respuestas:
¿Tu dual tiene que ser del género mínimo? Debido a que es trivial encontrar una incrustación celular para cualquier gráfico: simplemente elija un orden circular para los bordes que inciden en cada vértice, arbitrariamente, y luego determine las caras de la incrustación como secuencias de bordes consistentes con los ordenamientos elegidos.
Me gusta la representación GEM (mapa codificado por gráficos) de una incrustación del libro Fundamentos de la teoría de grafos topológicos de Bennington y Little. En esta representación, una incrustación está representada por un gráfico de 3 bordes de 3 colores regulares con un vértice por cada bandera de la incrustación (un triple incidente de vértice, borde y cara) y un borde por cada dos banderas que difieren en solo uno de los elementos de los conjuntos de vértices / aristas / caras que representan. Por ejemplo, la imagen a continuación de Wikipedia se puede interpretar como una GEM de un dodecaedro regular, en el que los ciclos rojos representan sus caras, los ciclos amarillos representan sus bordes y los ciclos azules representan sus vértices; Los bordes pueden ser coloreados de acuerdo con los colores de sus dos caras incidentes.
Dado un orden circular de los bordes de un gráfico G, su GEM se puede encontrar haciendo un ciclo de vértices 2d para cada vértice grado-d de G, dos para cada borde, con los pares de vértices para cada borde incidente que ocurre en el haga un ciclo en el orden circular elegido, y luego para cada borde e de G que une los dos pares de bordes GEM para los dos puntos finales de e en un rectángulo. Si desea una incrustación orientada, la elección de cómo vincular estos cuatro vértices en un rectángulo debe ser coherente con los ordenamientos circulares, de lo contrario puede ser arbitrario.
Luego, los vértices, bordes y caras de la incrustación de G están representados por ciclos en el GEM que alternan entre dos de los tres colores de borde. El dual de G está representado por un GEM con el mismo gráfico subyacente 3-regular pero con dos de sus colores de borde intercambiados. Y el gráfico representado por un GEM se puede formar contrayendo todos sus ciclos de vértices y fusionando pares de bordes paralelos en bordes únicos. Por lo tanto, construir un dual de G (siempre que no te importe qué dual) se puede hacer fácilmente en tiempo lineal.
fuente