Encontrando um duplo de um gráfico

11

De acordo com o livro Topological Graph Theory, de Gross e Tucker, dada a incorporação celular de um gráfico em uma superfície (por 'superfície', quero dizer aqui uma esfera com algumas pegas, e abaixo de S n se refere à esfera com exatamente n identificadores), pode-se definir uma multigraph dupla tratando as faces do gráfico original incorporando como vértices e adicionando uma aresta entre dois vértices para cada lado que as faces correspondentes têm em comum no gráfico original.n0Snn

Aqui está o meu problema . Dado um gráfico , preciso encontrar um outro gráfico G ' de tal modo que existe uma superfície S e um incorporação celular de L em S de modo a que G ' é o dual desta incorporação de L . Eu sei que existem muitos gráficos possíveis G ' ; Eu só preciso encontrar um para cada grafo G .GGSGSGGGG

Eu tenho várias perguntas . Minha estratégia atual é (1) determinar o gênero de G , (2) encontrar uma incorporação de G em S n e (3) encontrar a dualidade dessa incorporação. Todas essas etapas possuem algoritmos conhecidos (embora (1) seja NP-Hard). Gostaria de saber se existe uma maneira de encontrar um G ' que ignore a computação do gênero, já que esse é o gargalo dessa abordagem e essa é minha primeira pergunta. Minha segunda pergunta é: se eu sei que G é regular, isso pode facilitar o cálculo do gênero? E minha terceira pergunta é uma solicitação de referências que possam me ajudar a resolver esse problema.nGGSnGG

becko
fonte
Estou postando uma pergunta semelhante a necessidade de um simples gráfico de dupla aqui
Becko

Respostas:

17

O seu dual tem que ser do gênero mínimo? Como é trivial encontrar uma incorporação celular para qualquer gráfico: basta escolher uma ordem circular para as arestas incidentes em cada vértice, arbitrariamente, e depois determinar as faces da incorporação como as seqüências de arestas consistentes com as ordens escolhidas.

Gosto da representação GEM (mapa codificado em gráfico) de uma incorporação do livro Foundations of Topological Graph Theory, de Bennington e Little. Nesta representação, uma incorporação é representada por um gráfico 3-regular colorido de 3 arestas com um vértice para cada sinalizador da incorporação (um triplo incidente de vértice, aresta e face) e uma aresta para cada dois sinalizadores que diferem em apenas um dos elementos dos conjuntos de vértices / arestas / faces que eles representam. Por exemplo, a imagem abaixo da Wikipedia pode ser interpretada como um GEM de um dodecaedro comum, no qual os ciclos vermelhos representam suas faces, os ciclos amarelos representam suas bordas e os ciclos azuis representam seus vértices; as bordas podem ser coloridas de acordo com as cores das duas faces do incidente.

grande rhombicosidodecahedron

Dada uma ordenação circular das arestas de um gráfico G, seu GEM pode ser encontrado fazendo um ciclo de 2d vértices para cada vértice grau-d de G, dois para cada aresta, com os pares de vértices para cada aresta incidente ocorrendo no faça um ciclo na ordem circular escolhida e, em seguida, para cada aresta e de G, vincule os dois pares de arestas GEM dos dois pontos finais de e em um retângulo. Se você deseja uma incorporação orientada, a escolha de como vincular esses quatro vértices em um retângulo deve ser consistente com as ordenações circulares, caso contrário, pode ser arbitrária.

Em seguida, os vértices, arestas e faces da incorporação de G são representados por ciclos no GEM que alternam entre duas das três cores de aresta. O dual de G é representado por um GEM com o mesmo gráfico 3-regular subjacente, mas com duas de suas cores de borda trocadas. E o gráfico representado por um GEM pode ser formado contratando todos os seus ciclos de vértices e mesclando pares de arestas paralelas em arestas únicas. Portanto, construir um dual de G (contanto que você não se importe com qual dual) pode ser feito facilmente em tempo linear.

David Eppstein
fonte
11
Na verdade, o dual pode ser "construído" a partir da representação da gema em tempo zero , por uma simples conversão de tipo. A mesma estrutura de dados representa o mapa original e seu dual.
Jeffε
11
Além disso, para "escolher uma ordem circular para as arestas incidentes em cada vértice", recomendo usar a ordem na estrutura de dados da lista de adjacências que você está usando para representar o gráfico de qualquer maneira.
Jeffε
G
+1 Este post responde claramente à pergunta como eu a afirmei. Não sei se devo marcar isso como a resposta agora e iniciar uma nova postagem com o novo problema ou modificá-lo, pois o problema está claramente no contexto aqui.
Becko
11
Você sabe quantos vértices, arestas e faces possui, para poder calcular o gênero a partir da característica de Euler (com um pouco de cuidado para saber se a superfície é orientável ou não).
9309 David Eppstein