1
$\begingroup$

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?

  • 0
    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.2012-03-16
  • 0
    I am trying to identify some particular chains of a cubic planar graph (see http://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 (http://en.wikipedia.org/wiki/Planarity_testing), but is it possible to do something similar to identify left and right edges?2012-03-16
  • 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.2012-03-16
  • 0
    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!2012-03-16
  • 0
    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.2012-03-16

1 Answers 1

2

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.

  • 0
    What if you think of "left" and "right" as abstract labels? Is it possible to group the edges while I [walk this way](http://www.dailymotion.com/video/x2eu4x_aerosmith-run-dmc-walk-this-way_fun)?2013-08-18
  • 0
    @draks: I don't understand what you mean by "group the edges".2013-08-19