Trouver un double d'un graphique

11

Selon le livre Topological Graph Theory de Gross et Tucker, étant donné l'incorporation cellulaire d'un graphique sur une surface (par `` surface '', je veux dire ici une sphère avec quelques poignées, et ci-dessous réfère à la sphère avec exactement poignées), on peut définir une multigraphe double en traitant les faces du graphique d'origine en les incorporant comme des sommets et en ajoutant une arête entre deux sommets pour chaque côté que les faces correspondantes ont en commun dans le graphique d'origine.S n nn0Snn

Voici mon problème . Etant donné un graphe , je dois trouver un autre graphique tel qu'il existe une surface et un plongement cellulaire de sur tel que est le double de ce plongement de . Je sais qu'il existe de nombreux graphes possibles ; J'ai juste besoin de trouver un pour chaque graphique .G S G S G G G GGGSGSGGGG

J'ai plusieurs questions . Ma stratégie actuelle est de (1) déterminer le genre de , (2) trouver un plongement de sur , et (3) trouver le dual de ce plongement. Toutes ces étapes ont des algorithmes connus (bien que (1) soit NP-difficile). Je me demande s'il existe un moyen de trouver un qui contourne le calcul du genre, car c'est le goulot d'étranglement de cette approche, et c'est ma première question. Ma deuxième question est: si je sais que est régulier, cela peut-il faciliter le calcul du genre? Et ma troisième question est une demande de références qui peuvent m'aider à résoudre ce problème.G G S n G GnGGSnGG

Becko
la source
Je poste une question similaire nécessitant un simple graphique double ici
Becko

Réponses:

17

Votre duel doit-il être du genre minimum? Parce qu'il est trivial de trouver une incorporation cellulaire pour n'importe quel graphique: il suffit de choisir un ordre circulaire pour les arêtes incidentes à chaque sommet, arbitrairement, puis de déterminer les faces de l'incorporation comme des séquences d'arêtes cohérentes avec les ordres choisis.

J'aime la représentation GEM (carte codée graphiquement) d'une intégration du livre Foundations of Topological Graph Theory de Bennington et Little. Dans cette représentation, une incorporation est représentée par un graphique à 3 couleurs régulières à 3 arêtes avec un sommet pour chaque drapeau de l'incorporation (un triple incident de sommet, d'arête et de face) et une arête pour deux drapeaux qui diffèrent par un seul des éléments des ensembles sommet / arête / face qu'ils représentent. Par exemple, l'image ci-dessous de Wikipédia peut être interprétée comme un GEM d'un dodécaèdre régulier, dans lequel les cycles rouges représentent ses faces, les cycles jaunes représentent ses bords et les cycles bleus représentent ses sommets; les bords peuvent être colorés selon les couleurs de leurs deux faces incidentes.

grand rhombicosidodécaèdre

Étant donné un ordre circulaire des bords d'un graphique G, son GEM peut être trouvé en faisant un cycle de 2d sommets pour chaque sommet de degré d de G, deux pour chaque bord, avec les paires de sommets pour chaque bord incident se produisant dans le cycle dans l'ordre circulaire choisi, puis pour chaque arête e de G reliant les deux paires d'arêtes GEM pour les deux extrémités de e en un rectangle. Si vous voulez une incorporation orientée, le choix de la façon de lier ces quatre sommets dans un rectangle doit être cohérent avec les ordres circulaires, sinon il peut être arbitraire.

Ensuite, les sommets, les bords et les faces de l'incorporation de G sont représentés par des cycles dans le GEM qui alternent entre deux des trois couleurs de bord. Le dual de G est représenté par un GEM avec le même graphique à 3 sous-jacents mais avec deux de ses couleurs de bord inversées. Et le graphique représenté par un GEM peut être formé en contractant tous ses cycles de sommets et en fusionnant des paires d'arêtes parallèles en arêtes uniques. Ainsi, la construction d'un dual de G (tant que vous ne vous souciez pas du dual) peut facilement être effectuée en temps linéaire.

David Eppstein
la source
1
En fait, le dual peut être "construit" à partir de la représentation de la gemme en un rien de temps, par un simple transtypage. La même structure de données représente à la fois la carte d'origine et sa double.
Jeffε
1
De plus, pour "choisir un ordre circulaire pour les arêtes incidentes à chaque sommet", je recommande d'utiliser l'ordre dans la structure de données de la liste de contiguïté que vous utilisez pour représenter le graphique de toute façon.
Jeffε
@ Jɛ ff E et David Eppstein. Merci pour la réponse et les commentaires utiles. Je voulais terminer la programmation de cette approche GEM à mon problème avant de poster à nouveau ici. J'ai rencontré un problème, cependant. Le double graphe que j'obtiens est presque toujours un multigraphe. Comment éviter les multigraphes doubles? G
Becko
+1 Ce message répond clairement à la question telle que je l'ai posée. Je ne sais pas si je dois marquer cela comme la réponse en ce moment et commencer un nouveau message avec le nouveau problème, ou modifier ce message, car le problème est clairement dans son contexte ici.
Becko
1
Vous savez combien de sommets, d'arêtes et de faces vous avez, vous pouvez donc calculer le genre à partir de la caractéristique d'Euler (avec un peu de soin si la surface est orientable ou non).
David Eppstein