Timeline for Enumerating all inequivalent planar embeddings of a planar graph
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 14 at 4:58 | answer | added | Brendan McKay | timeline score: 2 | |
| Sep 19, 2023 at 17:56 | answer | added | didericis | timeline score: 2 | |
| Sep 19, 2023 at 1:17 | vote | accept | Licheng Zhang | ||
| Sep 19, 2023 at 1:17 | |||||
| Sep 16, 2023 at 9:01 | answer | added | Noam Zeilberger | timeline score: 4 | |
| Sep 16, 2023 at 5:11 | comment | added | Brendan McKay | "reset embedding" goes back to the original embedding, so clicking it twice is the same as clicking it once. It doesn't mean to use a different embedding. You can put a face of your choosing on the outside by clicking in it, but there is no way to show all the embeddings of a graph that isn't 3-connected. | |
| Sep 16, 2023 at 3:45 | comment | added | Licheng Zhang |
@BrendanMcKay Thanks. I know another software CaGe based on planari, which has option reset embedding. But this button often becomes unresponsive, even when there are more than one embedding of a given graph.
|
|
| Sep 15, 2023 at 14:34 | comment | added | Brendan McKay | Neither nauty nor plantri can solve this problem. Starting with one embedding, you can reach all the others using three operations. At a cutpoint you can flip over (take the mirror image) of one of the components (not drawn), or you can move one of the components into one of the other faces that meet at the cutpoint (your first example). At a cut of two vertices, you can flip one of the components over (like in your second example). But counting the number of distinct results depends on symmetries so it gets messy. | |
| Sep 15, 2023 at 13:10 | history | edited | gmvh | CC BY-SA 4.0 |
Corrected typo in title
|
| Sep 15, 2023 at 12:05 | comment | added | HenrikRüping | the Euler characteristic of that surface and only pick the ones which are spheres. I believe two embeddings are equivalent, iff they induce the same or exactly the opposite cyclic orderngs (opposite to deal with mirror images). | |
| Sep 15, 2023 at 12:02 | comment | added | HenrikRüping | I would try to start with the following approach. Any embedding of your graph induces a cyclic ordering on the set of edges at each vertex (just go through them counterclockwise). Given an arbitrary choice of cyclic ordering on the neighboring edges at each vertex, one can reconstruct where the 2-cells must have been. Glueing them in always gives a surface (any edge appears twiice and each link of a vertex also looks ok). Now the question is whether that surface is a sphere or a torus or ... One could write a computer program that goes through all the choices of cyclic orders and computes | |
| Sep 15, 2023 at 11:34 | history | edited | Licheng Zhang |
edited tags
|
|
| Sep 15, 2023 at 8:33 | history | edited | Licheng Zhang | CC BY-SA 4.0 |
deleted 3 characters in body
|
| Sep 15, 2023 at 8:22 | history | edited | Licheng Zhang | CC BY-SA 4.0 |
added 13 characters in body
|
| Sep 15, 2023 at 8:13 | history | asked | Licheng Zhang | CC BY-SA 4.0 |