Given a simple cycle of a planar graph, how could we verify whether is it a face of some planar embedding of the graph?
A graph may have more than one planar embedding, each with different faces.
I am looking for a solution that is relatively easy to implement on a computer using the existing toolkits.
Assuming that the cycle is simple:
One solution would be to add a new node that's connected to all the nodes in your cycle, and check that the extended graph is still planar. If it is, you can take the planar embedding* and remove your additions -- the cycle will now be a face.
*You may need to take the right embedding of the extended graph, that is, where the triangles made from an edge in the cycle and your new node are actually faces. But if they aren't you can take the additional stuff inside the triangle, and move it to the other side of the cycle edge, and then it's an actual triangular face. (This rewriting is not necessary to implement if all you need is to answer the existence question, though).
If the cycle is not simple, things get slightly more complex -- though if the original graph is 2-connected, only simple cycles can define faces.