Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite
1

Given a cubic planar graph, if I "walk" on one edge to get to a vertex, it it possible to know which of the other two edges is the left edge and which one is the right edge? Am I forced to draw the graph on paper, without edge crossing, and visually identify left and right edges?

share|improve this question
I don't understand the question. Surely whether it's possible to know this depends on what else you know? I think you'll need to say more about the scenario you're envisaging. – joriki Mar 16 '12 at 22:39
I am trying to identify some particular chains of a cubic planar graph (see 4coloring.wordpress.com/spiral-chains). To get these chains I was considering to convert the graph that I have into a graph theory model in memory (adjacency list) and then apply the algorithm to find the chain, but is it possible algorithmically to identify left and right edges? For example I know it is possible to use an algorithm to test planarity (en.wikipedia.org/wiki/Planarity_testing), but is it possible to do something similar to identify left and right edges? – Mario Stefanutti Mar 16 '12 at 23:20
1  
I'm still not sure I'm understanding you correctly. If I am, then the answer is no: This can't be possible, since you could draw the mirror image instead, and then left and right edges would be swapped, so they can't be determined by the abstract graph alone. – joriki Mar 16 '12 at 23:34
Your argument about mirroring the planar image of the graph convinced me. What a pity! I think I have to go the other way and elaborate the image by pattern recognition. In my case, since I have a particular kind of maps, it is not going to be so difficult. Thanks! – Mario Stefanutti Mar 16 '12 at 23:49
Some algorithms that tests planarity just try to fit the graph on the plane--if they succeed, the graph is planar (and then you can check if your edge is left or right having this particular drawing of graph on the plane), and if the graph is not planar, they fail. It may not be possible to say the edge is left or right just by looking at it, but it is definitely possible to do it in the case of some specific, arbitrarily chosen injection of the graph into the plane. – dtldarek Mar 16 '12 at 23:58

1 Answer

up vote 2 down vote accepted

My comment as an answer so it can be accepted:

The answer is no: This can't be possible, since you could draw the mirror image instead, and then left and right edges would be swapped, so they can't be determined by the abstract graph alone.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.