Incorporação de gráfico - Graph embedding

O gráfico de Heawood e o mapa associado embutidos no toro.

Em teoria gráfico topológico , uma incorporação (também escrito imbedding ) de um gráfico de uma superfície é uma representação em nos quais os pontos de estão associados com vértices e arcos simples ( homeomorfos imagens de ) estão associados com arestas , de tal maneira que:

  • os pontos finais do arco associado a uma aresta são os pontos associados aos vértices finais de
  • nenhum arco inclui pontos associados a outros vértices,
  • dois arcos nunca se cruzam em um ponto que seja interior a qualquer um dos arcos.

Aqui uma superfície é um compacto , conectado - colector .

Informalmente, a incorporação de um gráfico em uma superfície é um desenho do gráfico na superfície de tal forma que suas arestas podem se cruzar apenas em seus pontos finais. É bem sabido que qualquer grafo finito pode ser embutido no espaço euclidiano tridimensional . Um grafo plano é aquele que pode ser embutido no espaço euclidiano bidimensional

Freqüentemente, um embedding é considerado uma classe de equivalência (sob homeomorfismos de ) de representações do tipo que acabamos de descrever.

Alguns autores definem uma versão mais fraca da definição de "incorporação de grafos", omitindo a condição de não interseção para as arestas. Em tais contextos, a definição mais estrita é descrita como "incorporação de gráfico sem cruzamento".

Este artigo trata apenas da definição estrita de incorporação de gráficos. A definição mais fraca é discutida nos artigos " desenho gráfico " e " número cruzado ".

Terminologia

Se um gráfico está embutido em uma superfície fechada , o complemento da união dos pontos e arcos associados aos vértices e arestas de é uma família de regiões (ou faces ). Uma incorporação de 2 células , incorporação celular ou mapa é uma incorporação na qual cada face é homeomórfica a um disco aberto. Uma incorporação fechada de 2 células é uma incorporação em que o fechamento de cada face é homeomórfico a um disco fechado.

O gênero de um gráfico é o número inteiro mínimo de forma que o gráfico pode ser embutido em uma superfície do gênero . Em particular, um grafo planar tem gênero , porque pode ser desenhado em uma esfera sem autocruzamento. O gênero não orientável de um gráfico é o número inteiro mínimo de modo que o gráfico pode ser incorporado em uma superfície não orientável do gênero (não orientável) .

O gênero Euler de um gráfico é o número inteiro mínimo de modo que o gráfico pode ser incorporado em uma superfície orientável do gênero (orientável) ou em uma superfície não orientável do gênero (não orientável) . Um gráfico é orientavelmente simples se seu gênero Euler for menor do que seu gênero não orientável.

O gênero máximo de um gráfico é o número inteiro máximo de modo que o gráfico pode ser a célula embutida em uma superfície orientável do gênero .

Incorporação combinatória

Um grafo incorporado define com exclusividade as ordens cíclicas de arestas incidentes no mesmo vértice. O conjunto de todas essas ordens cíclicas é denominado sistema de rotação . Embeddings com o mesmo sistema de rotação são considerados equivalentes e a classe de equivalência correspondente de embeddings é chamada de incorporação combinatória (em oposição ao termo incorporação topológica , que se refere à definição anterior em termos de pontos e curvas). Às vezes, o próprio sistema de rotação é chamado de "incorporação combinatória".

Um grafo incorporado também define ordens cíclicas naturais de arestas que constituem os limites das faces da incorporação. No entanto, lidar com esses pedidos baseados em face é menos direto, pois, em alguns casos, algumas arestas podem ser atravessadas duas vezes ao longo de um limite de face. Por exemplo, este é sempre o caso para embeddings de árvores, que têm uma única face. Para superar esse incômodo combinatório, pode-se considerar que cada aresta é "dividida" longitudinalmente em duas "meias arestas" ou "lados". Segundo esta convenção, em todas as travessias de limite de face, cada meia-aresta é percorrida apenas uma vez e as duas meias-arestas da mesma aresta são sempre percorridas em direções opostas.

Outras representações equivalentes para embeddings celulares incluem o gráfico de fita , um espaço topológico formado pela colagem de discos topológicos para os vértices e bordas de um gráfico incorporado e o mapa codificado por gráfico , um gráfico cúbico de cor de borda com quatro vértices para cada borda de o gráfico incorporado.

Complexidade computacional

O problema de encontrar o gênero de gráfico é NP-difícil (o problema de determinar se um gráfico de -vertex tem gênero é NP-completo ).

Ao mesmo tempo, o problema do gênero de grafos é tratável por parâmetros fixos , ou seja, algoritmos de tempo polinomial são conhecidos para verificar se um grafo pode ser embutido em uma superfície de um dado gênero fixo, bem como para encontrar o embutimento.

O primeiro avanço nesse sentido aconteceu em 1979, quando algoritmos de complexidade de tempo O ( n O ( g ) ) foram submetidos de forma independente ao Simpósio Anual ACM de Teoria da Computação : um de I. Filotti e GL Miller e outro de John Reif . Suas abordagens eram bastante diferentes, mas por sugestão do comitê do programa, eles apresentaram um documento conjunto. No entanto, Wendy Myrvold e William Kocay provaram em 2011 que o algoritmo fornecido por Filotti, Miller e Reif estava incorreto.

Em 1999 foi relatado que o caso do gênero fixo pode ser resolvido no tempo linear no tamanho do gráfico e duplamente exponencial no gênero.

Embeddings de gráficos em espaços de dimensões superiores

Sabe-se que qualquer grafo finito pode ser embutido em um espaço tridimensional.

Um método para fazer isso é colocar os pontos em qualquer linha no espaço e desenhar as arestas como curvas, cada uma delas situada em um semiplano distinto , com todos os semiplanos tendo essa linha como seu limite comum. Uma incorporação como essa, em que as bordas são desenhadas em meiosplanos, é chamada de incorporação de livro do gráfico. Essa metáfora vem da imaginação de que cada um dos planos onde uma borda é desenhada é como a página de um livro. Observou-se que de fato várias bordas podem ser desenhadas na mesma "página"; a espessura do livro do gráfico é o número mínimo de meiosplanos necessários para tal desenho.

Alternativamente, qualquer gráfico finito pode ser desenhado com arestas retas em três dimensões sem cruzamentos, colocando seus vértices na posição geral de forma que nenhum quatro seja coplanar. Por exemplo, isto pode ser conseguido através da colocação da i th vértice no ponto ( i , i 2 , i 3 ) da curva de momento .

Uma incorporação de um gráfico em um espaço tridimensional no qual nenhum dos dois ciclos está topologicamente vinculado é chamada de incorporação sem links . Um gráfico tem uma incorporação sem links se e somente se não tiver um dos sete gráficos da família Petersen como menor .

Galeria

Veja também

Referências