Encontrar un dual de un gráfico

11

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 nn0Snn

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 GGGSGSGGGG

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 GnGGSnGG

llamar
fuente
Estoy publicando una pregunta similar que requiere un gráfico dual simple aquí
becko

Respuestas:

17

¿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.

gran rombicosidodecaedro

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.

David Eppstein
fuente
1
En realidad, el dual se puede "construir" a partir de la representación de gemas en tiempo cero , mediante un simple tipo de conversión. La misma estructura de datos representa tanto el mapa original como su dual.
Jeffε
1
Además, para "elegir un orden circular para los bordes que inciden en cada vértice", recomiendo usar el orden en la estructura de datos de la lista de adyacencia que está utilizando para representar el gráfico de todos modos.
Jeffε
@ Jɛ ff E y David Eppstein. Gracias por la respuesta y comentarios útiles. Quería terminar de programar este enfoque GEM para mi problema antes de volver a publicar aquí. Sin embargo, me he encontrado con un problema. El gráfico dual que estoy obteniendo es casi siempre un multigrafo. ¿Cómo puedo evitar los multigrafos dobles? G
Becko
+1 Esta publicación responde claramente la pregunta tal como la dije. No sé si debería marcar esto como la respuesta en este momento y comenzar una nueva publicación con el nuevo problema, o modificar esta publicación, ya que el problema está claramente en contexto aquí.
Becko
1
Usted sabe cuántos vértices, aristas y caras tiene, por lo que puede calcular el género a partir de la característica de Euler (con un poco de cuidado sobre si la superficie es orientable o no).
David Eppstein