Implementations of planar graphs/maps (with embeddings)

Question

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.)

Hatbox

The surface of a sphere has a Euler Characteristic of 2; this is the same as the Euler Characteristic for a 2D plane so any planarity test that embeds a graph onto a 2D plane can be mapped to embed on to the surface of a sphere. A simple mapping from one to the other would be to draw a circle around the graph on the flat plane and then the centre of the circle maps to the north pole on the sphere and the perimeter of the circle maps to the south pole on the sphere and you can use polar coordinates within the circle on the 2D plane to map directly to the latitude/longitude on the sphere. – Denitrify

@Denitrify I am aware that embedding a graph in the plane and in the sphere is equivalent. This question is about implementations of combinatorial maps (a graph together with an equivalence class of planar embeddings). – Hatbox

Answer 1

I have just noticed that networkx does contain a class for the purpose I describe, namely PlanarEmbedding. See https://networkx.github.io/documentation/latest/reference/algorithms/planarity.html

(I am not certain whether this has been introduced since I asked the question, or whether I missed it at the time.)

The methods that come with the class do seem to be quite basic, and this only implements one of the possible data structures for planar embeddings. I will investigate further; if anyone knows of other implementations, that information would be appreciated.

Hatbox

In fact, having looked at this a little bit, I think this data type still does not allow for multiple edges, and hence is not suitable for my purposes. (I have ended up writing my own ad-hoc solution.) – Hatbox

Answer 2

I'm not sure I completely understand your requirement, but have you looked at this planarity library. It is a cython wrapper to a c(++?) implementation of planarity algorithms, including drawing. I've been using it with networkX.

Unread

Thanks - I've taken a look at this, as I'm (finally) returning to the project I was interested in this for. However, as far as I can tell from the examples, the planarity library does not contain a data structure that actually encodes the (combinatorial) embedding. – Hatbox