Timeline for For a Planar Graph, Find the Algorithm that Constructs A Cycle Basis, with each Edge Shared by At Most 2 Cycles
Current License: CC BY-SA 2.5
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 5, 2010 at 7:04 | vote | accept | Graviton | ||
| Dec 4, 2010 at 3:37 | comment | added | Sam Nead | @ Jukka - I think (think!) that I've answered your question in the affirmative. I've posted it as an answer to OP's question. | |
| Dec 2, 2010 at 8:51 | comment | added | Jukka Suomela | By the way, can we show that finding a cycle basis like this is at least as difficult as finding a planar embedding? Given the cycle basis, can we easily construct a planar embedding? | |
| Dec 2, 2010 at 4:48 | comment | added | David Eppstein | Yes. I would have also suggested Brandes' preprint "the left-right planarity test", another simplified variant of a planarity testing, but unfortunately he seems to have locked it. | |
| Dec 2, 2010 at 2:35 | comment | added | Graviton | @Peter and David, by planar embedding algorithm I assume that you mean algorithm such as Boyer and Myrvold? | |
| Dec 2, 2010 at 2:17 | comment | added | David Eppstein | Each edge is in at most two faces, the ones found by walking in this way from its two orientations. (If it is a bridge, both orientations are part of a single face.) Actually this part is true for any cyclic orientation of edges around each vertex of any graph. The part that requires planarity to prove is the fact that the faces form a cycle basis. | |
| Dec 2, 2010 at 2:15 | comment | added | Peter Shor | The hard part is hidden in the phrase "Finding planar embeddings is linear time but complicated; there are several standard algorithms." You need to use one of these complicated algorithms. | |
| Dec 2, 2010 at 1:57 | comment | added | Graviton | @David, I see. But I afraid that this algorithm won't guarantee that any edge is shared by at most two faces? And what if at w there are more than 2 edges connected to it? which edge to choose then? | |
| Dec 2, 2010 at 1:47 | comment | added | David Eppstein | From oriented edge uv, look in the cyclic order at v to find the next edge vw. Then look in the cyclic order at w to find the next edge wx, etc. When you get back to uv, you've found one face. Do it for all orientations of all edges, and you find all faces. | |
| Dec 2, 2010 at 1:18 | comment | added | Graviton | @David, not to sure what you mean here. I think my goal is to determine the face. So the face is not known beforehand. How can I walk from edge to edge around each face ? | |
| Dec 2, 2010 at 1:14 | comment | added | David Eppstein | Yes, just walk from edge to edge around each face using the cyclic ordering to tell you which edge to walk to at each step. | |
| Dec 2, 2010 at 1:11 | history | edited | David Eppstein | CC BY-SA 2.5 |
added 59 characters in body
|
| Dec 2, 2010 at 1:10 | comment | added | Graviton | @David, are you saying that I can construct planar embedding and read off the polygonal faces without assigning the coordinates to vertex? Do you have a paper ( or even better, code!!) for these kinds of algorithm? | |
| Dec 2, 2010 at 1:00 | history | answered | David Eppstein | CC BY-SA 2.5 |