Um gráfico planar é um gráfico que pode ser incorporado no plano, sem ter arestas de cruzamento.
Seja um hipergrafo k -uniforme, isto é, um hipergrafo de modo que todas as suas hiperedições tenham tamanho k.
Houve algum trabalho realizado na incorporação de hipergrafos no plano (com o contexto de cluster ou outro aplicativo), mas geralmente os dados não podem ser incorporados no plano. A solução pode ser forçá-lo, com alguma perda, ou incorporá-lo em uma dimensão superior, como sugiro aqui:
Uma extensão natural de planaridade (IMO, pelo menos) é um " incorporação -simples-" (existe um nome diferente conhecido por isso?) De L : uma incorporação de H : X → R k , de tal modo que existem superfícies que ligam todos os vértices de cada hiper-borda e estes não se cruzam, exceto os pontos de extremidade.
(Pense no analógico em 2D, onde cada superfície é uma aresta que você pode desenhar da maneira que desejar).
Aqui está um exemplo de uma incorporação 3-simples válida de um hipergrafo 3-uniforme. (Cada vértice é colorido pelas hiperedges em que está contido e cada face representa uma hiper-borda).
Outro exemplo de gráfico de 3 simples é o hipergrafo de 3 uniformes completo em 5 vértices . Para ver isto simplesmente tomar 4 pontos em R 3 , que não se encontram em um plano 2D, criar uma pirâmide triangular (casco convexo), e coloque o quinto ponto no centro da pirâmide, ligando-o a outros vértices.
Da mesma forma, parece que o hipergrafo 3 uniforme completo em 6 vértices não possui uma incorporação 3 simples.
Existem algumas propriedades muito úteis dos gráficos planares que permitem algoritmos aprimorados para problemas difíceis quando o gráfico é plano. Infelizmente, os dados geralmente não são planos, embora às vezes sejam de baixa dimensionalidade. Penso que a compreensão de quais propriedades dos gráficos planares generalizam nos ajudará a descobrir quais algoritmos podem ser adaptados para dimensões mais altas com a mesma ferramenta.
Um exemplo de uma propriedade que pode ser útil vem do Teorema de Fáry, que sugere que todo gráfico plano pode ser incorporado de maneira que todas as suas arestas sejam segmentos de linha reta.
Existem outras propriedades que podem ser generalizadas? por exemplo, a fórmula de Euler para gráficos planares pode ser generalizada de alguma forma para uma dimensão mais alta? (embora, no momento, não tenha certeza de qual seria o significado disso).