Geração de gráficos de perímetro modo que os ciclos mínimos formem uma cobertura de borda dupla

Seja . Preciso gerar gráficos simples de circunferência modo que o conjunto de todas as -cycles forme uma cobertura de borda dupla de (ou seja, toda aresta é compartilhada por exatamente duas -cycles), e de modo que a interseção de duas -cycles é um vértice, uma aresta ou vazio. Os gráficos gerados devem ser arbitrariamente grandes.$g\geq 3$$G$$g$$g$$G$$g$$g$

O método de geração deve ter alguma aleatoriedade, mas não em um sentido trivial. Quero poder obter gráficos bastante complicados. Por exemplo, imagine uma grade retangular no plano. Se identificarmos os lados opostos do retângulo delimitador, obteremos um gráfico que satisfaz todos os requisitos acima para . Eu qualificaria este gráfico como simples.$n\times m$$g=4$

Existe algum método desse tipo?

Todas as referências a problemas semelhantes também são apreciadas.

Minha idéia meio cozida era um pouco ambiciosa. Incluí-o abaixo para referência, mas a condição de distância especificada não é suficiente para garantir uma circunferência grande.

Existem mapas de superfície altamente simétricos arbitrariamente grandes e com grande perímetro, mas as provas de existência publicadas são amplamente baseadas na teoria de grupos e não na topologia ou na geometria em si.

Especificamente, para quaisquer números inteiros , , e tais que , existe um mapa de superfície regular em que toda face possui arestas, todo vértice tem grau e todo não contratável o ciclo na superfície cruza pelo menos arestas. Aqui significa "regulares" , tanto que cada vértice tem o mesmo grau e que, para qualquer par de arestas dirigidas, existe um automorfismo da incorporação que envia dirigido borda para o outro. Definir suficientemente grande nesta construção garante que a circunferência do gráfico seja . Veja, por exemplo:d r 1 / g + 1 / d < 1 / 2 g d r r $g$$d$$r$$1/g + 1/d < 1/2$$g$$d$$r$$r$$g$

• Roman Nedela e Martin Škoviera. Mapas regulares em superfícies com grande largura plana. European J. Combinatória 22 (2): 243--262, 2001.

• Jozef Širáň. Representações de grupos de triângulos e construções de mapas regulares. Proc. London Math. Soc. 82 (3): 513-532, 2001.

Depois de ter um desses mapas de superfície, mapas maiores com a mesma circunferência e grau podem ser gerados através da construção de espaços de cobertura.

Aqui está uma maneira (semi-cozida) de gerar esses gráficos. Seja um gráfico plano com as seguintes propriedades:$G$

• Toda face delimitada de tem exatamente arestas.$G$$g$

• A face externa de tem um número par de arestas; chamar estas as bordas do limite de . (Essa condição é mantida automaticamente quando é par; se é ímpar, deve ter um número par de faces delimitadas.)G g g $G$$G$$g$$g$$G$

• É possível emparelhar as arestas de limite de , de modo que a distância em de qualquer aresta de limite até seu parceiro seja pelo menos . Essa condição não é realmente suficiente; a condição exata necessária aqui não é clara.G g$G$$G$$g$

Gráficos de plano arbitrariamente grandes com essas propriedades podem ser construídos tomando uma porção finita suficientemente grande de uma telha regular do plano hiperbólico por gons$g$ .

Finalmente, para obter um gráfico de superfície onde cada face possui comprimento , identifique pares de arestas de contorno em acordo com o emparelhamento descrito acima. As faces delimitadas de se tornam as faces de uma incorporação celular de em alguma superfície fechada sem limites. A condição de distância no emparelhamento garante que a circunferência de seja  . g L L L ' L '$G'$$g$$G$$G$$G'$$G'$$g$

Ao escolher e o emparelhamento com mais cuidado, uma vez é possível construir gráficos - regulares arbitrariamente grandes que satisfaçam sua condição de perímetro, para quaisquer números inteiros e tais que . Mesmo dentro dessas restrições, a construção tem muitos graus de liberdade.d d g 1 / d + 1 / g < 1 /$G$$d$$d$$g$$1/d + 1/g < 1/2$