As you are computing a list of all faces of the graph as a list of oriented walks along their arcs (as you've written) you could compute the area of the face (polygon) efficiently as is suggested in the second algorithm here (since you have plane coordinates of the vertices): Area of polygon. The face with largest area should be the outer face of your graph.

About using information only in the combinatorial map, I think Noam Zeilberger is right about that they can be embedded in different ways on the plane. More information about this may be here: Polynomial Algorithms for Subisomorphism of nD Open Combinatorial Maps

As you are computing a list of all faces of the graph as a list of oriented walks along their arcs (as you've written) you could compute the area of the face (polygon) efficiently as is suggested in the second algorithm here (since you have plane coordinates of the vertices): Area of polygon. The face with largest area should be the outer face of your graph.

About using information only in the combinatorial map, I think Noam Zeilberger is right about that they can be embedded in different ways on the plane. More information about this may be here: Polynomial Algorithms for Subisomorphism of nD Open Combinatorial Maps