For the purpose of this post, by a plane graph, or a planar map, I will mean an abstract graph that can be drawn in the plane (or equivalently on the sphere), together with the circular order of the edges at every vertex according to a particular such drawing. This extra information determines the embedding on the sphere (up to moving vertices and edges in such a way that they never intersect any other vertices / edges). I do want to allow loops and multiple edges.
For example, suppose that we have build a graph as follows. Draw two vertices (A and B) in the plane, together with two edges connecting these two. The two edges together form a simple closed curve \gamma. Now add two more vertices, A' and B', and connect A and A' with an edge, and B and B' also.
This abstract graph will have two inequivalent embeddings, according to whether the vertices A' and B' are separated by the curve \gamma or not.
My question is: Is there a Python package that implements such plane graphs?
I am interested in a package that can create a drawing of a plane graph (respecting the embedding, of course), as well as execute some standard operations (e.g. give the number of faces, form a dual graph etc.)
If such a package does not exist in Python, I would also be interested in implementations in other languages.
Of course there are various packages that implement the drawing of graphs, and graph-theoretic algorithms. However, I did not notice in any of these the possibility of working with graphs that already come with an embedding. A reference would be much appreciated.
EDIT. Let me elaborate a little further. Two embeddings of the same graph in the sphere are equivalent if they are related by a homeomorphism of the sphere to itself. As mentioned above, the embedding of a planar graph is not unique, in general, so what I am asking is not the same as testing a graph for planarity and drawing some embedding thereof.
There are several combinatorial ways of encoding embeddings up to this equivalence. Probably the simplest is to record the cyclic order of edges at each vertex ("rotation system"), but there are many others. See the article on graph embeddings on Wikipedia for a discussion and references.
There are obvious operations that one may wish to carry out on such a combinatorial embedding, e.g. find the faces of the graph, find the faces an edge/vertex is adjacent to, insert a vertex in a face, subdivide an edge, draw a picture of the embedding etc.
Is there an implementation of one or several of these data structures representing combinatorial graph embeddings available in Python? (I remark that graph embeddings make sense on general surfaces, although I am primarily interested in the case of the sphere.)
