Timeline for Enumerating all inequivalent planar embeddings of a planar graph
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 19, 2023 at 1:17 | vote | accept | Licheng Zhang | ||
| Sep 19, 2023 at 1:17 | |||||
| Sep 16, 2023 at 13:12 | comment | added | Brendan McKay | I had a student who solved a related problem, namely to generate planar graphs, up to usual graph isomorphism, by identifying the graph with a unique embedding out of all its planar embeddings. It was successful but very complicated. | |
| Sep 16, 2023 at 13:10 | comment | added | Brendan McKay | The labelling method I described is used internally in plantri, but it hasn't been developed into a program to solve this particular problem as far as I know. I find the approach somewhat unsatisfying because one has to keep the known planar maps in order to compare against them. Sometimes there could be quite a lot. A better solution would be to understand the symmetries of the original well enough to know in advance which other embeddings will be equivalent. But this sounds nontrivial. (continued) | |
| Sep 16, 2023 at 12:57 | comment | added | Noam Zeilberger | Thanks for the comments and I completely agree that this approach will only work "in principle" for small graphs. So then the procedure you suggest (1. start with a planar embedding of the graph, 2. apply the flip/move operations in all possible ways, 3. remove duplicates using a DFS/BFS) would yield a much more efficient solution to the original question, wouldn't it? But you wrote that "Neither nauty nor plantri can solve this problem." Is it just that this specific functionality hasn't been implemented, although it could be implemented in principle? | |
| Sep 16, 2023 at 12:33 | comment | added | Brendan McKay | In terms of equivalence testing, there are linear-time algorithms but they are impractical. The map can be uniquely labeled with respect to a root flag by using DFS or BFS from that flag using the embedding to determine the order of visiting neighbours. Then a canonical form of the map is the lexicographically best of those labellings. With some heuristics to help, it can be made almost linear on average with a very small constant. | |
| Sep 16, 2023 at 12:24 | comment | added | Brendan McKay | The problem is that for graphs of even modest size the number of combinatorial embeddings is vastly greater than the number which are planar. It is much more efficient to generate just the planar ones by the operations I listed in a comment above, which can be described in terms of $(\alpha,\sigma)$ if you wish. Consider cubic planar graphs, where there are exponentially many embeddings but as little as 2 that are planar. | |
| Sep 16, 2023 at 9:01 | history | answered | Noam Zeilberger | CC BY-SA 4.0 |