Incorporação combinatória de um gráfico

12

Aqui: http://www.planarity.org/Klein_elementary_graph_theory.pdf (em captações de capítulos) é dada uma definição de incorporação combinatória de um gráfico planar. (com definição de faces e assim por diante) Embora possa ser facilmente usado para qualquer gráfico, eles definem o gráfico planar como o gráfico, para o qual a fórmula de Euler mantém (assumindo que o gráfico esteja conectado). É compreensível que, para cada gráfico de plano, a definição de faces na incorporação combinatória seja semelhante à definição de faces na incorporação topológica. (assumindo que o gráfico esteja conectado. Caso contrário, na incorporação combinatória, teremos uma superfície infinita para cada componente conectado)

A questão é: se, para algum gráfico conectado, a incorporação combinatória satisfaz a fórmula de Euler, isso significa que esse gráfico é planar no sentido topológico (possui incorporação plana, ou seja, é gráfico plano )?

graph-theory co.combinatorics planar-graphs Finsky
fonte
Mais adiante neste artigo, eles respondem que isso é possível. Mas alguém pode dar alguns links para a prova?
Finsky 14/09/12

Respostas:

16

Isso é realmente menos sobre gráfico em si e mais sobre topologia. Uma incorporação combinatória define um distribuidor múltiplo, um espaço topológico em que cada ponto tem uma vizinhança homeomórfica a um disco aberto bidimensional: a incorporação permite que uma face seja definida e podemos definir um espaço topológico escolhendo um disco para cada cole-os ao longo das bordas do gráfico. Um teorema bem conhecido em topologia (chamado de classificação de 2 variedades) nos diz exatamente quais 2 variedades são possíveis, e todas são distinguíveis entre si, sejam elas orientáveis ​​ou tenham a mesma característica de Euler (ou ambas ) - consulte http://www.maths.ed.ac.uk/~aar/surgery/zeeman.pdfpara algumas notas de aula razoáveis ​​sobre esse assunto, que incluem a prova que você está pedindo. Não existem outros 2-manifolds nessa classificação que tenham a mesma característica de Euler que a esfera; portanto, se você calcular a característica de Euler e achar que ela corresponde à fórmula de uma esfera, você sabe que sua incorporação deve estar em uma esfera.

Encontrar uma incorporação com coordenadas geométricas reais no plano, uma vez que você tenha uma incorporação combinatória planar, não é inteiramente trivial, mas pode ser feito, por exemplo, usando a teoria das madeiras de Schnyder. Tenho algumas notas de aula sobre isso em http://www.ics.uci.edu/~eppstein/gina/schnyder/, por exemplo.

David Eppstein
fonte
Muito obrigado por uma resposta tão extensa! Eu li o primeiro artigo e parece que entendi a prova. Mas eu tenho uma pergunta: tudo isso significa que, se definiremos superfícies como quisermos (quero dizer algum subconjunto arbitrário de arestas, não como na incorporação combinatória com ordem e outras coisas no sentido anti-horário), cole-as todas de uma maneira que cola está apenas compartilhando arestas de 2 superfícies, define 'nós' resultantes nos pontos finais das arestas como vértices E se a fórmula de Euler se mantiver, este é um gráfico planar?
Finsky 14/09/12
1
Você deve ter cuidado para obter um coletor: as faces da incorporação devem ser discos topológicos, não é permitido deixar arestas sem cola, cada aresta deve ser colada apenas a uma outra aresta e, em cada vértice, deve haver apenas um ciclo de bordas e faces coladas ao redor (não é o que você ganha se cola dois cones nas pontas). Além disso, você precisa começar com um gráfico conectado ou contar a característica de Euler para cada componente separadamente. Mas se tudo isso é verdade, e a fórmula de Euler se mantém, então sim, é planar.
David Eppstein
Sim, esqueci esses casos, com certeza eles também devem aguentar. Muito obrigado!
Finsky 15/09/12