8
$\begingroup$

In a planar graph $G$, one can easily find all the cycle basis by first finding the spanning tree ( any spanning tree would do), and then use the remaining edge to complete cycles. Given Vertex $V$, edge $E$, there are $C=E-V+1$ number of cycles, and there are $C$ number of edges that are inside the graph, but not inside the spanning tree.

Now, there always exists a set of cycle basis such that each and every edge inside the $G$ is shared by at most 2 cycles. My question is, is there any algorithm that allows me to find such a set of cycle basis? The above procedure I outlined only guarantees to find a set of cycle basis, but doesn't guarantee that all the edges in the cycle basis is shared by at most two cycles.

Note: Coordinates for each vertex are not known, even though we do know that the graph must be planar.

  • 0
    Find a planar embedding (there should be plenty of algorithms) and use the faces. This is in effect the same as the other answer. You could also try constructing the dual of the graph directly, if faster algorithms for that exist.2010-11-30
  • 0
    @Moron It seems strange to use acual embeddings for something so algebraic-looking. Maybe there is a more direct algorythm? Also, what is an algorythm for embedding? Are the faces easy to determine from it?2010-11-30
  • 0
    @Max: Finding planar embeddings of a planar graph is a well known problem. Google should find plenty for you. Yes, the faces should be easy to determine once we have the embedding. I agree, maybe there is a better algorithm, and that is the reason I left a comment, instead of an answer.2010-11-30
  • 0
    @Moron, is it possible to provide a link? I did a google search on the terms you suggested ( planar embedding faces) but I don't think they are helpful at all2010-12-01
  • 0
    @Ngu: Don't add faces to the search. Just do planar embedding.2010-12-01
  • 0
    @Moron, I search for "planar embedding" and one of the link I get is [this](http://www.cs.huji.ac.il/~dolev//pubs/planar-embed.pdf). I don't quite understand the content but the impression I get from it is that it requires one to know the area of the graph in order to find the thing I want, which means we need to know the coordinates. But for my application, I don't know the coordinates that are assigned to each vertex.2010-12-01
  • 0
    @Ngu: No, the paper you linked is talking about the area occupied by the graph after a planar embedding is found. For cycle finding, it does not matter whether the area is quadratic etc. Try searching for graph layout algorithms too.2010-12-01
  • 0
    @Moron, I afraid I still couldn't get it. Is it possible to point me to a paper, or a webpage that is helpful here? Sorry for the trouble.2010-12-01
  • 0
    @Ngu: Perhaps this is helpful: http://bkocay.cs.umanitoba.ca/g&g/articles/readsalgorithm.pdf (also see the references). Note what I said was just a suggestion (hence a comment) and I am not even sure it will work.2010-12-01
  • 0
    @Moron, I read about your planar embedding thing and the paper you suggest. It occurs to me that mainly it has to do with how to draw a graph **nicely** on paper-- I don't see how that leads to face determination. I mean, I can't instruct the computer to draw graph on paper and then inspect visually what are the faces of the graph2010-12-01
  • 0
    @Ngu: I am guessing reference [4] in that paper will be helpful to you. Drawing on paper = assigning coordinates. Once you have the coordinates, you should be able to construct the polygon faces, using some computational geometry algorithms. I would suggest you try cstheory.stackexchange.com. Sorry, can't help you more.2010-12-01
  • 0
    @Moron, actually my application does have coordinates for each vertex. It's just that I don't want to use them because I believe without coordinates I can do what I want to do. Thanks anyway.2010-12-02
  • 0
    @Ngu: Did you check out the Reference [4] I talked about above? I just looked at cstheory and David Eppstein seems to be saying the same thing (finding the ordering of edges around a vertex).2010-12-02

2 Answers 2

5

To suppliment Aryabhata's comment: yes, using plane embedding algorithm will do. One of such algorithm is Boyer and Myrvold.

5

I agree with all the commenters who say that you should just find a planar embedding. However, I happened to stumble across a description that might make you happy:

Let $G$ be a three-connected planar graph and let $C$ be a cycle. Let $G/C$ be the graph formed by contracting $C$ down to a point. Then $C$ is a face of the planar graph if and only if $G/C$ is two-connected.

In particular, this lemma is useful in proving that a three-connected graph can only be planar in one way, a result of Whitney.

But testing this for every cycle is much less efficient than just finding the planar embedding.