Incorporation combinatoire d'un graphe

12

Ici: http://www.planarity.org/Klein_elementary_graph_theory.pdf (dans le chapitre plongements) est donnée la définition de l' intégration combinatoire d'un graphe planaire. (avec définition des faces, etc.) Bien qu'il puisse être facilement utilisé pour n'importe quel graphe, ils définissent le graphe plan comme le graphe, pour lequel la formule d'Euler tient (en supposant que le graphe est connecté). Il est assez compréhensible que pour chaque graphique plan , la définition des faces en intégration combinatoire soit similaire à la définition des faces en intégration topologique. (en supposant que le graphique est connecté. Sinon, dans l'intégration combinatoire, nous aurons une face infinie pour chaque composant connecté)

La question est: si pour un graphe connecté son incorporation combinatoire satisfait la formule d'Euler, cela signifie-t-il que ce graphe est plan au sens topologique (il a une intégration plane, c'est-à-dire qu'il est un graphe plan )?

Finsky
la source
Plus loin dans cet article, ils répondent que cela est possible. Mais peut-on donner des liens vers la preuve?
Finsky

Réponses:

16

C'est vraiment moins sur le graphique en soi que sur la topologie. Une intégration combinatoire définit une variété à 2, un espace topologique dans lequel chaque point a un voisinage homéomorphe à un disque ouvert à 2 dimensions: l'incorporation permet de définir une face, et nous pouvons définir un espace topologique en choisissant un disque pour chaque face et les coller ensemble le long des bords du graphique. Un théorème bien connu en topologie (appelé la classification des 2-variétés) nous dit exactement quelles sont les 2 variétés possibles, et elles se distinguent toutes les unes des autres, qu'elles soient orientables ou qu'elles aient la même caractéristique d'Euler (ou les deux) ) - voir http://www.maths.ed.ac.uk/~aar/surgery/zeeman.pdfpour quelques notes de cours raisonnables sur ce sujet, qui incluent la preuve que vous demandez. Il n'y a pas d'autre 2 variétés dans cette classification qui ont la même caractéristique d'Euler que la sphère, donc si vous calculez la caractéristique d'Euler et trouvez qu'elle correspond à la formule d'une sphère, vous savez que votre incorporation doit être sur une sphère.

Trouver un plongement avec des coordonnées géométriques réelles dans le plan, une fois que vous avez un plongement combinatoire planaire, n'est pas tout à fait trivial mais peut être fait par exemple en utilisant la théorie des bois de Schnyder. J'ai quelques notes de cours à ce sujet sur http://www.ics.uci.edu/~eppstein/gina/schnyder/ par exemple.

David Eppstein
la source
Merci beaucoup pour une réponse aussi complète! J'ai lu le premier papier et il semble que j'en ai compris la preuve. Mais il me reste une question: cela signifie-t-il que si nous définissons des surfaces comme nous le souhaitons (je veux dire un sous-ensemble arbitraire d'arêtes, pas comme dans une intégration combinatoire avec un ordre anti-horaire et d'autres choses), les coller tous ensemble de telle manière que la colle est uniquement sur le partage des bords de 2 surfaces, définissez les «nœuds» résultants aux extrémités des bords en tant que sommets ET si la formule d'Euler est vraie, ceci est un graphique plan?
Finsky
1
Vous devez faire attention à ce que vous obteniez un collecteur: les faces de l'incorporation doivent être des disques topologiques, vous n'êtes pas autorisé à laisser des bords non collés, chaque bord ne doit être collé qu'à un autre bord, et à chaque sommet, il ne doit y avoir que un cycle de bords et de visages collés autour de lui (pas comme ce que vous obtenez si vous collez deux cônes ensemble à leurs pointes). Vous devez également commencer par un graphique connecté ou compter séparément la caractéristique d'Euler pour chaque composant. Mais si tout cela est vrai et que la formule d'Euler est vraie, alors oui, c'est planaire.
David Eppstein du
Ouais, j'ai oublié ces cas, bien sûr qu'ils doivent tenir aussi. Merci beaucoup!
Finsky