Construction d'un embeddage plan à partir de sommets rigides

Question

J'ai une liste de sommets avec un ordre cyclique sur leurs arêtes (sommets rigides).

Remarque sur les sommets rigides

Je ne sais pas à quel point le concept de sommets rigides est répandu, et cela aide à les illustrer. Comme le montre l'image, les rotations ($1 \to 2$) et réflexions ($2 \to 3$) des arêtes sont autorisées, car ces opérations conservent l'ordre cyclique. Pourtant ($3 \to 4$) modifie l'ordre cyclique du sommet, donc ce n'est plus le même sommet rigide.

Je sais pertinemment que pour cet ensemble de sommets rigides, il est possible de leur donner un graphe planaire incorporant et de maintenir leur ordre cyclique, car dans le problème sur lequel je travaille, les sommets proviennent des croisements d'un nœud, et des arêtes proviennent des brins entre les croisements.

Ceci est relativement facile à faire à la main pour un nombre suffisamment petit de sommets. Je fais cela par essais et erreurs, en dessinant des sommets avec une orientation particulière et en voyant où ils s'insèrent dans ce que j'ai dessiné jusqu'à présent, et en apportant des modifications si nécessaire. Mais je n'ai pas d'algorithme pour faire cela, et cela devient plus difficile pour un plus grand nombre de sommets.

Exemple

L'ensemble des sommets rigides
$(L, H, A, G)$,
$(H, B, I, A)$,
$(B, F, C, E)$,
$(J, D, K, C)$,
$(D, L, E, K)$,
$(F, J, G, I)$

Incorporer comme [Embeddage de sommet rigide]
(Cet exemple est relativement facile à faire à la main.)

J'aimerais trouver un algorithme pour, ne connaissant que l'ensemble des sommets rigides (comme dans l'exemple), incorporer les sommets de manière plane sans changer l'ordre cyclique, de préférence d'une manière implémentable sur un ordinateur.

Answer 1

Si les données proviennent d'un nœud (plutôt que d'un lien), il s'agit du problème classique des mots de Gauss. Il existe un certain nombre d'algorithmes en temps linéaire pour déterminer les sommets à inverser pour obtenir un diagramme plan (et il y en a aussi beaucoup pour les liens). Un article que je connais est

Rosenstiehl, Pierre; Tarjan, Robert E. , codes de Gauss, graphes hamiltoniens planaires et permutations triables par pile , J. Algorithms 5, 375-390 (1984). ZBL0588.68034 .

et à un moment donné, je l'ai implémenté (même si je ne peux pas dire que je me souviens précisément comment utiliser ce code). Les données d'entrée de l'algorithme sont essentiellement un code DT (Dowker-Thistlethwaite), moins les informations de sur / sous-croisement. Par exemple, voici une conversion des données que vous avez fournies en un code DT:

Le format d'entrée spécifique dans le programme lié prend le code DT au format

[Start 5, Start 8, Start 9, Start 6, Start 11, End 5,
 Start 3, Start 10, End 8, End 9, End 10, End 11]

(Chacun Startet Endest comme une paire de parenthèses correspondantes, dont le type est indexé par un entier. L'algorithme met les parenthèses dans deux classes afin que, dans chaque classe, les parenthèses correspondent bien. Vous pouvez lire hors de l'incorporation planaire d'une manière directe à partir de la classe de chaque sommet.)

Si vous ne vous souciez pas des algorithmes de temps linéaire, alors il existe un algorithme exponentiel naïf où vous considérez tous $2^n$ flips du $n$sommets et calculez le genre pour chacun. Il est simple de calculer le genre d'une carte combinatoire , car tout ce que vous avez à faire est de compter le nombre de faces puis de calculer$1-\frac{1}{2}(V-E+F)$, en supposant que le diagramme est connecté. Si cette quantité est$0$, alors vous avez trouvé un ensemble de retournements qui aboutissent à un encastrement planaire.

En ce qui concerne le dessin, j'ai réussi à faire une subdivision barycentrique du polyèdre associé à l'incrustation planaire, puis à calculer une incrustation Tutte . La subdivision barycentrique rend les bords pliables, ce qui rend l'encastrement plus agréable. Cela aide également le graphique à satisfaire l'exigence de 3-connectivité pour que l'incorporation Tutte soit une incorporation.

(J'ai du code pour le faire, mais malheureusement, il n'est pas encore dans un état partageable. Une fois que ce sera, espérons-le plus tard cette année, je vais essayer de me souvenir de mettre à jour cette réponse.)