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.
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 .
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.
Respostas:
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.
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.
fonte