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
    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
    @draks: I don't understand what you mean by "group the edges".2013-08-19