Timeline for Find all faces in a graph from list of edges
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 14, 2014 at 22:40 | vote | accept | JMcPherson | ||
| Oct 29, 2014 at 22:46 | comment | added | Brendan McKay | @Alex : Yes of course, but the question is only about embeddings in the plane. | |
| Oct 29, 2014 at 11:43 | comment | added | Alex Degtyarev | @BrendanMcKay A cyclic order at each vertex (ribbon graph structure) defines a unique embedding to a closed oriented surface; if we are lucky, this surface is a sphere. On the other hand, given a ribbon graph structure, the regions are immediate (as orbits of an appropriate group action); in particular, so is the Euler characteristic hence the genus of the surface containing the graph. Then, if this happens to be $S^2$, it's entirely up to us which region is to be called unbounded. | |
| Oct 29, 2014 at 11:15 | comment | added | Tony Huynh | en.wikipedia.org/wiki/Rotation_system | |
| Oct 29, 2014 at 11:11 | comment | added | Brendan McKay | The cyclic order of edges at each vertex uniquely defines an embedding on a sphere. For the plane you have to additionally say which face is on the outside. | |
| Oct 29, 2014 at 9:45 | comment | added | Federico Poloni | @bof This seems to help, but only if one considers also the 'outside' of the graph as a face (i.e., 1265 in the graph in the left). Otherwise you can just put 3,4,5,2 in this order in the middle column to have a counterexample. Is this enough? I am not sure; intuitively, yes, but we'd probably need an answer from someone more knowledgeable than me in this field. | |
| Oct 29, 2014 at 9:31 | comment | added | bof | What if the neighbors of each vertex are listed in counterclockwise order, i.e., the neighbors of 1 are 2,5,4,3 on the left, and 2,5,3,4 on the right? I guess that's enough to determine the embedding, isn't it? | |
| Oct 29, 2014 at 9:30 | vote | accept | JMcPherson | ||
| Oct 29, 2014 at 9:31 | |||||
| Oct 29, 2014 at 9:25 | history | edited | Federico Poloni | CC BY-SA 3.0 |
images
|
| Oct 29, 2014 at 9:23 | comment | added | JMcPherson | If that is the case, what extra information would be needed make the problem solvable? I probably should have mentioned this before (and will update the question), but it is also safe to assume that the graph is both planar and connected. | |
| Oct 29, 2014 at 9:16 | history | answered | Federico Poloni | CC BY-SA 3.0 |